动态规划算法

维基百科简述

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、电脑科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

分析流程

• 状态定义：根据问题特征划分阶段，确定dp[i]代表的逻辑

• 列出状态方程：一般是f(n)与前后子函数相关的方程

• 初始状态：dp[0]、dp[1]等等一般是前几个作为初始值

• 遍历顺序:正序或者反向遍历

• 返回坐标:返回dp[n]，最后一个元素值

• 简化空间复杂度：有些问题可以用一些临时变量来存储中间值，降低空间复杂度

部分步骤可以根据实际问题做简化。

例子

看概念很难理解，所以举几个简单的例子来看看动态规划是怎么用的。

斐波那契数列

斐波那契数列问题就是典型的动态规划问题。

• 状态定义：数组中dp[i]就是代表数列的第i个数字
• 转移方程：dp[i+1] = dp[i] + dp[i-1]
• 初始值：dp[0]=0, dp[1]=1
• 返回值：dp[n]，数列最后一个也就是第n个元素的值
• 空间优化：用局部变量存储临时值，减小空间复杂度

public int fib(int n) {
    int dp[] = new int[n];
    dp[0] = 0;
    dp[1] = 1;
    for (int i=2; i<=n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9

然后我们可以发现，dp[i-1] 和 dp[i-2] 可以用临时变量来存储，不需要dp数组，能把空间复杂度从O(n)降低到O(1)。

public int fib(int n) {
    /*if (n<2) return n;
    int a=0, b=1, sum=0;
    for (int i=2; i<=n; i++) {
        sum = a+b;
        a = b;
        b = sum;
    }
    return sum;*/
    // 继续简化，可读性较差
    int a=0, b=1, sum=0;
    for (int i=0; i<n; i++) {
        sum = a+b;
        a = b;
        b = sum;
    }
    return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Integer Break

https://leetcode.com/problems/integer-break/

整数拆分并计算乘积，求最大的乘积，也就是剪绳子问题，只能按整数分段剪。

• 状态定义：dp[i]表示长度为i剪成m段的最大乘积
• 转移方程：
  • 剪成两段，剪j长度作为一段，乘积就是 j*(i-j)
  • 大于两段，剪j长度作为多段，那么 dp[i] = dp[j]*(i-j)
  • 综上，转移方程：dp[i] = Math.max(j*(i-j), dp[j]*(i-j))
• 初始值：dp[1]=1
• 返回值 dp[n]

class Solution {
    public int integerBreak(int n) {
        //因为dp下表从0开始，dp[0]是第一个，dp[n]是n+1个
        int dp[] = new int[n+1];
        //2 <= n <= 58，不管dp[1]
        //m段，m>1，1x1=1
        dp[2] = 1;
        //i表示绳子长度，从3开始，小于3不用算了乘积都是1
        for (int i=3; i<=n; i++) {
            //j表示第一次剪去的长度，剩余i-j
            //小于等于 i-2 是因为最后是 j*1 等于 j，没意义
            for (int j=1; j<=i-2; j++) {
                //两段直接相乘，或者i-j继续分段，比较取最大值
                //int tmp = Math.max(dp[i-j]*j, (i-j)*j);
                int tmp = Math.max(dp[i-j], (i-j)) * j;
                //和前一个dp比较取最大值
                dp[i] = Math.max(tmp, dp[i]);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

其他典型的例子还有剪绳子和打家劫舍问题。

House Robber

• 状态定义：dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额
• 转移方程：设n间房子，前n间最大偷窃价值dp[n]，前n-1就是dp[n-1]，再偷一间房子（第n+1间）价值为num
  • 偷第n+1个房子，因为有不能偷相邻房子的限制，第n间房子就不能偷了，那么dp[n+1]=dp[n-1]+num
  • 不偷第n+1个房子，那么dp[n+1]=dp[n]
  • 综上，转移方程：dp[n+1]=max(dp[n],dp[n−1]+num)
• 初始值：0间房子偷窃价值dp[0]=0
• 返回值：dp最后一个，所以房子偷窃价值
• 用局部变量存储临时值，减小空间复杂度

public int rob(int[] nums) {
    int len = nums.length;
    if (len == 0) return 0;
    int dp[] = new int[len+1];
    dp[0] = 0;
    dp[1] = nums[0];
    for(int i=1; i<len; i++) {
        dp[i+1] = Math.max(dp[i], dp[i-1]+nums[i]);
    }
    return dp[len];
}
1
2
3
4
5
6
7
8
9
10
11

空间优化：

class Solution {
    public int rob(int[] nums) {
        // f(n) = Math.max(f(n-1), f(n-2)+num)
        // n1->n-1, n2->n-2
        int n1=0, n2=0, tmp;
        for (int num : nums) {
            tmp = n1;
            n1 = Math.max(n2+num, n1);
            n2 = tmp;
        }
        return n1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

原文链接。访问我的个人网站查看更多文章。