Dynamic Programming

原文链接

动态规划中，状态和状态转移方程

Set Min[i] equal to Infinity for all of i
Min[0] = 0

For i = 1 to S
For j = 0 to N-1
	if (Vj<=i AND Min[i-Vj]+1]<Min[i])
Then Min[i] = Min[i-Vj] + 1

Output Min[S]

func upper_bound(arr []int, s, e, key int) int {
	if arr[e] < key {
		return e + 1
	}
	mid := 0
	for s < e {
		mid = s + (e-s)/2
		if arr[mid] < key {
			s = mid + 1
		} else {
			e = mid
		}
	}
	return s
}

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	end := make([]int, 0)
	end = append(end, nums[0])
	l := 1

	for i := 1; i < len(nums); i++ {
		pos := upper_bound(end, 0, len(end)-1, nums[i])
		if pos > len(end)-1 {
			end = append(end, nums[i])
			l++
		} else {
			end[pos] = nums[i]
		}
	}

	return l
}

二维的DP问题

状态S[i][j]表示我们走到(i, j)这个格子时，最多能收集到多少个苹果。那么， 状态转移方程如下：

S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)

其中i代表行，j代表列，下标均从0开始；A[i][j]代表格子(i, j)处的苹果数量。

带额外条件的DP问题

无向图G有N个结点，它的边上带有正的权重值，过路最短问题

迪杰斯特拉，最短路径问题

当阅读一个题目并且开始尝试解决它时，首先看一下它的限制。 如果要求在多项式时间内解决，那么该问题就很可能要用DP来解。遇到这种情况， 最重要的就是找到问题的“状态”和“状态转移方程”。(状态不是随便定义的， 一般定义完状态，你要找到当前状态是如何从前面的状态得到的， 即找到状态转移方程)如果看起来是个DP问题，但你却无法定义出状态， 那么试着将问题规约到一个已知的DP问题(正如“高级”一节中的例子一样)。