动态规划问题

初级问题

动态规划问题的关键是找到状态以及状态转移方程。这里有一些很好的讨论：https://www.zhihu.com/question/23995189

初级问题

如果我们有面值为 1 元、3 元和 5 元的硬币若干枚，如何用最少的硬币凑够 11 元？

例如这个题目，我们可以从如果要凑够 1 元，3 元，5 元最少需要多少的硬币呢？显然答案是 1，因为我们有对应面值的硬币。到这里我们应该可以看出来了，我们可以定义状态 dp(i) 为凑够面值为 i，需要的最少硬币为多少。

下面，我们就需要找到状态是如何从小的问题，转化为大的问题的。也就是找到状态转移方程。举一个简单的例子。当 i 为 6 时，我们可以一眼看出为 dp(6) = 2(也就是 2 枚 3 元的)。反映方程上我们应该如何找到 dp(6)呢？其中 6 可以由(1, 5), (2, 4), (3, 3) 得到，也就是 dp(6) = dp(1) + dp(5) 或 dp(6) = dp(2) + dp(4) 或 dp(6) = dp(3) + dp(3) 得到，所以答案就是它们的最小值。

现在
```
dp(i) = min(dp(i-j) + dp(j)), j ∈ [1, i/2]
```
而初始状态有：
```
dp(1) = 1
dp(3) = 1
dp(5) = 1
```
下面是代码的实现：
```
def Min(n):
    dp = {1:1, 3:1, 5:1}
    for i in range(1, n + 1):
        try:
            if dp[i]:
                continue
        except KeyError:
            temp = []
            for j in range(1, i // 2 + 1):
                temp.append(dp[i-j] + dp[j])
            dp[i] = min(temp)
    return dp[n]
```
一个序列有 N 个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。还是如上一个找到状态以及状态转移方程。这里的状态我们定义 d(i) 为以 A[i] 结尾最长非降子序列的长度。显然 dp(1) = 1, 转移方程定义如下：

\[dp(i)=\left\{ \begin{aligned} dp(i-1)+1 & , & if & & A[i]>A[i-1] \\ 1 & , & if & & Others \end{aligned} \right.\]

简单的写下代码如下：
```
s = [5, 3, 4, 8, 6, 7]

dp = {0: 1}
m = 1
for i in range(1, len(s)):
    try:
        if dp[i]:
            continue
    except KeyError:
        if s[i] > s[i - 1]:
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = 1
    if dp[i] > m:
        m = dp[i]
print "m: ", m
```

Zigzag 问题来源 TopCoder

这个问题相比与上面的两个要复杂一些，因为状态多了，看着要麻烦些。还是按照套路来，找状态和转移方程。我们定义 z(i, 0) 为第 i 个值比前面值大时的最长 zigzag 序列长度。同样定义 z(i, 1)为第 i 个值比前面值小时的最长 zigzag 序列长度。有：

z(0, 0) = 1
z(1, 0) = 1

z(i, 0) = max(z(j, 1) + 1), 其中 j < i, A[j] < A[i]
z(i, 1) = max(z(j, 0) + 1), 其中 j < i, A[j] > A[i]

代码如下：

def Zigzag(l):
    z = {}
    z[0, 0] = 1
    z[0, 1] = 1
    m = 0
    for i in range(len(l)):
        if not z.get((i, 0), None):
            z[i, 0] = 0
        if not z.get((i, 1), None):
            z[i, 1] = 0
        for j in range(i):
            if l[i] > l[j]:
                z[i, 0] = max(z[j, 1] + 1, z[i, 0])
            if l[i] < l[j]:
                z[i, 1] = max(z[j, 0] + 1, z[i, 1])

        m = max(m, max(z[i, 0], z[i, 1]))

    return m

http://www.hawstein.com/posts/dp-novice-to-advanced.html http://www.hawstein.com/posts/dp-knapsack.html http://www.cnblogs.com/wuyuegb2312/p/3273337.html http://www.cnblogs.com/wuyuegb2312/p/3281264.html https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114 https://www.zybuluo.com/Yano/note/253649

动态规划问题

Table of Contents

初级问题