Skip to content

动态规划

维基百科简述

动态规划(英语: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];
}

然后我们可以发现,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;
}

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];
    }
}

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

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];
}

空间优化:

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;
    }
}