DynamicProgramming专题

发表于   |   更新于 | 分类于

动态规划算法毫无疑问是算法题目中最具有挑战性且最常考的问题之一，本质是建立在dfs的思路基础上并对其加以优化。在此也对leetcode动态规划题加以梳理和总结

1. 题目特点

  1. 计数型
    • 有多少种方式走到右下角
    • 有多少种方法选出k个数使得和是Sum
  2. 求最大最小值
    • 从左上角走到右下角路径的最大数字和
    • 最长上升子序列长度
  3. 求存在性
    • 取石子游戏，先手是否必胜
    • 能不能选出k个数使得和是Sum

出现这些题型，基本就是往动态规划的方向去想，当然还有类如贪心之类的算法

image-20210104154440844

比如出现题B这种问题类型，根本不用往动态规划上想

2. 与dfs的联系

以509. 斐波那契数为例：

以递归的方式求解非常容易理解：

1
2
3
4
5
public int fib(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    return fib(n-1)+fib(n-2);
}

but! 有一个显而易见的问题！！ 即递归的指数爆炸式搜索！！

image-20210104155331889

如图是想要求出x=5时的斐波那契数的递归过程，其实本质上也就是一棵树的dfs，可以看出fib（4）的左子树和fib（5）的右子树是重合的，fib（4）的右子树和fib（3）的左子树是重合的，这里进行的就是一次重复计算，也就是刚才提到的指数爆炸

再来看dp的方式如何求解：

1
2
3
4
5
6
7
8
9
public int fib(int n){
    List<Integer> ans= new ArrayList<>();
    ans.add(0);
    ans.add(1);
    for(int i=2; i<=n; i++){
        ans.add(ans.get(i-1)+ans.get(i-2));
    }
    return ans.get(n);
}

3. 思想

将多个决策划分为多次决策

graph LR
状态1-->|决策1|状态2-->|决策2|状态3-->|决策3|状态4

涉及到：状态、阶段、决策、状态转移方程，“最优值函数”。

image-20210211165438762

这是最能体现多个决策与多步决策思想的题目：

多个决策：将所有的路径暴力罗列，进行比较

多步决策：按照图中所示进行分层，从左到右（或者从右到左），每层的最短路径都可以通过上一层的最短路径得到，这样一步一步的得到终点的最短路径

image-20210211181757968

4. 组成部分

4.1 确定状态

简单的说就是，接动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么

确定状态需要两个意识：

  • 最后一步
  • 子问题

4.2 状态转移方程

F[x] = min{F[X-1],F[X-2],F[X-5]}

4.3 初始条件和边界条件

4.4 计算顺序

4.5 空间优化

对新开的dp数组进行压缩，以f[i] = f[i-1]+1为例，通过滚动的方式，只需要维持一个长度为2的数组就可以实现f[i]的更新

5. 坐标型动态规划

特征

  1. 最简单的动态规划类型
  2. 给定一个序列或网格
  3. 需要找到序列中某个/些子序列或网格中的某条路径
    • 某种性质最大/最小
    • 计数
    • 存在性
  4. 动态规划方程dp[i]中的下标i表示以$a_i$为结尾的满足条件的子序列的性质，f[i][j]中的下标i，j表示以格子（i，j）为结尾的满足条件的路径的性质
    • 最大值/最小值
    • 个数
    • 是否存在

例题

1. 最长递增子序列

  • 确定状态：

    • 最后一步：对于最优的策略，一定有最后一个元素a[j]

    • 第一种情况：最优策略中最长连续上升子序列就是{a[j]}，答案是1

      第二种情况：子序列长度大于1，那么最优策略中a[j]前一个元素肯定是a[j-1]。这种情况一定值a[j-1]<a[j]

    • 因为是最优策略，那么选中的以a[j-1]结尾的连续上升子序列一定是最长的

  • 转移方程

    • dp[j] = 以a[j]结尾的最长连续上升子序列的长度

      dp[j] = max{ 1, dp[j-1]+1 | ( j>0 && a[j-1]<a[j] ) }

  • 边界情况如上，初始条件为1

  • 计算顺序：0,1,2,3,4，。。。

    和硬币组合题不一样的是，最终答案并不一定是dp[n-1]，而是从dp数组中取最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0]=1;
        int max = 0;
        for(int i=1; i<nums.length; ++i){
            if(nums[i]>nums[i-1]){
                dp[i] = dp[i-1]+1;
            }else{
                dp[i] = 1;
            }
        }
        for(int i=0; i<nums.length; ++i){
            if(dp[i]>max) max = dp[i];
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//空间优化
int[] dp  = new int[2];
int old = now = 0;
int max = 0;
for(int i=1; i<nums.length; ++i){
    if(nums[i]>nums[i-1]){
        old = now;
        now = 1-now;
        dp[now] = dp[old]+1;
    }else{
        dp[now] = 1;
    }
    if(dp[now]>max) max = dp[now];
}
return dp[now];

2. 最小路径和

  • 确定状态

    最优策略的路径总和最小

    • 若倒数第二部（i-2,j-1），则前面一定是从（0，0）到达（i-2,j-1）的最小路径
    • 倒数第二部（i-1,j-2）亦然

    子问题：从（0,0）走到（i,j）的路径最小数字总和f[i][j]

  • 状态转移方程：f[i][j] = min{f[i-1][j], f[i][j-1]}

  • 初始条件和状态转移方程：

    • 初始条件：f[0][0] = grid[0][0]
    • 边界情况：i=0或者j=0 , 则前一步只能有一个方向过来

  • 计算顺序：

    计算第0行，计算第2行。。。

1
2


3. 炸弹袭击

求四个方向上一共能炸死多少人，可以拆分为单一方向然后求和，这样就可以应用动态规划求解，以炸弹向上炸为例：

  • 确定状态

    • 假设有敌人或有墙的地方也能放炸弹

    • 有墙的格子：炸弹炸不到格子外面

    在（i,j）格子放炸弹，能够炸到的最多人数：

    • 该格子是人：炸到的人数（i-1,j）+1，
    • 该格子是空：炸到的人不变(i-1,j)
    • 该格子是墙：0；

    子问题：求(i-1,j)向上能炸到的最大人数

    状态：up[i][j]表示向上能炸到的最大人数

  • 状态转移方程

    image-20210218160958700

  • 初始条件和边界情况：第0行的up值和格子内容相关

  • 计算顺序，逐行计算

6. 序列+位操作型动态规划

位操作型

和位操作相关的动态规划一般用值做状态

1. 比特位计数

  • 确定状态

    最后一步：观察这个数最后一个二进制位（最低位），去掉它，看剩下多少个1

    要求N的二进制中有多少个1，将N的二进制去掉最后一位（N %2），设新的数是Y = N>>1

    子问题：求Y得二进制有多少1

    状态：f[i]表示i的二进制表示中有多少位1

  • 状态转移方程

    f[i] = f[i>>1]+i%2

  • 初始条件和边界条件：

    f[0] = 0

  • 计算顺序0,1,2,3，。。。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num+1];
        dp[0] = 0;
        for(int i=1;i<=num;++i){
            dp[i] = dp[i>>1] + (i%2);
        }
        return dp;
    }
}

序列型

和坐标型的比较

  • 状态

    序列型：动态规划方程f[i]中的下标i表示前i个元素a[0],a[1],a[2],...a[i-1]的某种性质

    坐标型：f[i]表示以a[i]结尾的某种性质，或者说与a[i]的性质有关，如

    • 最长递增子序列：考虑nums[i]是否比nums[i-1]大
    • 炸弹袭击：考虑grid[i][j]是人，空，还是墙

  • 初始化

    序列型：f[0]表示空序列的性质

    坐标型：f[0]表示以$a_0$为结尾的某种性质，即$a_0$本身就是一个子序列

1. 粉刷房子

2. 打家劫舍 II

3. 买卖股票的最佳时机 III

4. 买卖股票的最佳时机 IV

7.划分型

1. 完全平方数

2. 分割回文串 II

* 延展：回文串的判断方法

image-20210304210241466

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
boolean[][] isPalin = new boolean[n][n];
int i, j, t;
for(int t=0; t<n; ++t){
    //奇数长度回文串的生长情况
    i=j=t;
    while(i>=0 && j<n && str1[i]==str[j]){
        isPalin[i][j] = true;
        --i;
        ++j;
    }
    //偶数长度回文串的生长情况
    i = t; j = t+1;
    while(i>=0 && j<n && str1[i]==str[j]){
        isPalin[i][j] = true;
        --i;
        ++j;
    }
}
//isPalin[i][j]表示从第i个字符到第j个字符是回文串

8. 博弈型

唯一一个不考虑最后一步，而是从第一步开始推算的类型

1. Coins in a Line

image-20210307192814282

image-20210307192914209

image-20210307192924112

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean firstWillWin(int n) {
        if(n == 0) return false;
        if(n == 1 || n == 2) return true;
        boolean[] b = new boolean[n+1];
        b[0] = false;
        b[1] = true;
        b[2] = true;
        for(int i=3; i<=n; ++i){
            b[i] = (b[i-1] == false) || (b[i-2] == false);
        }
        return b[n];
    }
}