【算法日记】从零开始认识动态规划（一）

1 动态规划问题

1.1 什么是动态规划算法

动态规划（Dynamic Programming），简称DP。动态规划的核心是依次解决子问题，通过状态转化得到最终的结果。也就是说，针对可以划分成若干子问题的问题，我们可以使用动态规划来进行解决。

动态规划的解题思路基本一致：

1. 分析问题，确定dp表的意义
2. 推导状态转移方程
3. 根据状态转移方程确定处理顺序
4. 完成dp表的初始化问题
5. 进行处理

这其中最重要的就是对状态转移方程的推导，只有确定好了状态转移方程，才能正确的处理问题。推导状态转移方程时，可以借助画图来进行辅助！只有确定了状态转移方程 ，才能进行初始化，因为状态转移方程决定了dp数组要如何初始化！

后面的讲解中我都是围绕着这五点来进行讲解。

可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题⽬就解出来了。其实 确定递推公式仅仅是解题里的⼀步而已！

1.2 动态规划算法如何Debug

对于动态规划的题目，有些时候自己写不出来，看一眼题解的状态转移方程，然后改到自己的代码中就稀里糊涂的通过了。这样的debug方式肯定是有问题的！这是一种非常不好的习惯！对于dp的理解千万不能是处于黑盒的状态，一定要理解状态转移方程的含义，而不能死记硬背！

当提交不能通过时，那么肯定是状态转移方程出现了问题，对此最直观的方式就是将dp表打印出来。根据dp表的结果与预期结果进行比对，来查看状态转移中哪里出现了错误！

当使用动态规划解决问题时，出现了错误就要扪心自问：

• 这道题目我举例推导状态转移公式了么？
• 我打印dp数组的日志了么？
• 打印出来了dp数组和我想的⼀样么？

1.3 动态规划算法模型

在动态规划问题中是有一些常见模型的，我们整的这些模型进行分类学习，这样效率更高！

1. 斐波那契数列模型
2. 路径问题
3. 简单多状态问题：买卖股票时机模型，打家劫舍模型
4. 子数组，子序列问题
5. 回文串问题
6. 背包问题

我们依次介绍，逐个解决！

2 斐波那契数列模型

这里给出斐波那契数列的题单：

1. 1137. 第 N 个泰波那契数
2. 面试题 08.01. 三步问题
3. 746. 使用最小花费爬楼梯
4. 91. 解码方法

经典的斐波那契数列大家也都熟悉了：
$T[i]=T[i-1]+T[i-2](i>1)$是其推导的公式，解决类斐波那契数列问题时，一般都会明确给出状态转移方程，我们可以根据其简单的解除出问题！

我们按照动态规划的解题步骤：

1. 分析问题，确定dp表的意义：$T[i]$表示第i个泰波那契数为多少
2. 推导状态转移方程：$T[i]=T[i-1]+T[i-2]+T[i-3](i>2)$
3. 根据状态转移方程确定处理顺序：从左往右进行处理
4. 完成dp表的初始化问题：$T[0]=0$ ，$T[1]=1$ ，$T[2]=1$
5. 进行处理

class Solution {
public:
    int tribonacci(int n) {
        if(n < 3)
        {
            if(n == 0) return 0;
            else if(n == 1) return 1;
            else if(n == 2) return 1;
            else return 0;
        }
        vector<int> cnt(n + 1);
        cnt[0] = 0;
        cnt[1] = 1;
        cnt[2] = 1;
        for(int i = 3 ; i <= n ; i++)
            cnt[i] = cnt[i - 3] + cnt[i - 2] + cnt[i - 1];
        return cnt.back();
    }
};

这样就很简单的解决了问题！

我们再来看一道稍微综合一些的题目：

在这道题目中并没有给出明确的状态转移方程，所以要我们自己分析。我们按照动态规划的步骤进行处理：

1. 分析问题，确定dp表的意义：$dp[i]$表示该位置为结尾的字符串有几种解析方法。
2. 推导状态转移方程：对于一个位置来说，有两种解析方式，可以单独解析，也可以和前一个数字组合进行解析。那么对于一个位置$dp[i]=dp[i-1]+dp[i-2]$。当然是有限定条件的，必须可以进行解析才可以进行计算！
3. 根据状态转移方程确定处理顺序：从前向后进行处理
4. 完成dp表的初始化问题：将$dp[0]$,$dp[1]$根据实际情况进行赋值
5. 进行处理

class Solution {
public:
    int numDecodings(string s) {
        //动态规划
        //进行初始化
        vector<int> dp(s.size() , 0);
        dp[0] = s[0] != '0';
        if(s.size() == 1) return dp[0];

        if(s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0')*10 + s[1] - '0';
        if( 10 <= t && t <= 26) dp[1] += 1;

        //进行处理
        for(int i = 2 ; i < s.size() ; i++)
        {
            //解析一个数字
            if(s[i] != '0') dp[i] += dp[i - 1];
            //解析两个数字
            int t = (s[i-1] - '0') * 10 + s[i] - '0';
            if( 10 <= t && t <= 26) dp[i] += dp[i-2];
        }

        return dp[s.size() - 1];
    }
};

3 路径问题

路径问题题单：

1. 62. 不同路径
2. 63. 不同路径 II
3. LCR 166. 珠宝的最高价值 （原：剑指 Offer 47. 礼物的最大价值）
4. 931. 下降路径最小和
5. 64. 最小路径和
6. 174. 地下城游戏

路径问题我们之前接触过，可以使用深度优先搜索$(dfs)$ 或者 广度优先搜索$(bfs)$进行处理！而对于动态规划来说，路径问题实质上是一种二维DP，需要在一张地图表上进行依次处理。

来看经典的不同路径问题：

按照动态规划解题步骤进行解决：

1. 分析问题，确定dp表的意义：$dp[i][j]$表示机器人到底（i， j）位置有几种路径
2. 推导状态转移方程：机器人只能向下或向右移动，对于一个位置来说有两种方式到达：
   $dp[i][j]=dp[i-1][j]+dp[i][j-1]$需要注意的是位置要有意义！所以可以将dp表向外扩大一圈，这样就不需要处理繁琐的边界条件了！
3. 根据状态转移方程确定处理顺序：从机器人起始位置进行处理！
4. 完成dp表的初始化问题：每个位置都初始化为零，start左边或者上边初始化为1，这样处理start就是1了！
5. 进行处理

class Solution {
public:
    int uniquePaths(int m, int n) {
        //动态规划解决
        //首先总结状态转换方程
        //走到第（i,j）位置有两种方法从 (i-1 , j) (i , j-1)走过来
        //T(i , j) = T(i-1 , j) + T(i , j-1)
        //进行初始化 --- 只需要初始化(0 , 1)位置即可
        // 0 1 0 0 0
        // 0 
        vector<vector<int>> dp(m+1 , vector<int>(n+1 , 0));
        dp[0][1] = 1;
        for(int i = 1 ; i < m+1 ; i++)
        {
            for(int j = 1 ; j < n+1 ; j++)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

在这道题的基础上，63. 不同路径 II 加入了障碍物，需要我们进行处理。我们只需要真的障碍物进行特殊处理即可！

然后我们再来看，在路径问题的基础上，有增加了一个维度：原数组的意义。这种问题需要我们不仅要进行路径的处理，还要考虑该位置的最优解。以LCR 166. 珠宝的最高价值 为例：

我们要找到具有最高价值的一条路径，我们按照动态规划的思路进行解决：

1. 分析问题，确定dp表的意义：$dp[i][j]$表示到底（i， j）位置的最高价值
2. 推导状态转移方程：每次只能向下或向右移动，对于一个位置来说有两种方式到达：
   $dp[i][j]=max(dp[i-1][j],dp[i][j-1])+nums[i][j]$ 需要注意的是位置要有意义！所以可以将dp表向外扩大一圈，这样就不需要处理繁琐的边界条件了！
3. 根据状态转移方程确定处理顺序：从起始位置进行处理！
4. 完成dp表的初始化问题：每个位置都初始化为零，这样处理start就是nums[starti][startj]了！
5. 进行处理

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        //动态规划解决
        //T(i,j) = max(T(i-1,j) , T(i,j-1)) + f(i , j)
        //首先建表解决初始化问题
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> dp(m+1 , vector<int>(n+1 , 0));
        //进行处理
        for(int i = 1 ; i < m+1 ; i++)
        {
            for(int j = 1 ; j < n+1 ; j++)
            {
                dp[i][j] = max(dp[i-1][j] ,  dp[i][j-1]) + frame[i-1][j-1];
            }
        }

        return dp[m][n];
    }
};

接下来我们来看一道正难则反的题目：174. 地下城游戏

这道题的难点在于如果从勇士位置进行处理的话，由于我们不知道后续格子上会有什么数字，所以不知道该位置应该选择前面较大的值还是较小的值（选较大的可能后续会超血量，选择较小有可能就死了）。所以我们从公主位置进行处理，$dp[i][j]$表示从(i , j)走到终点至少需要多少血量，这样处理通过与下两个位置进行比较，就可以得出该位置的最小血量了！得到的一定是准确的！

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) {
        //动态规划解决问题
        //建表进行初始化
        int m = d.size();
        int n = d[0].size();
        //dp表 --- 表示从这里走到终点至少需要多少血量
        vector<vector<int>> dp(m+1 , vector<int>(n+1, INT_MAX));
        dp[m][n-1] = 1;
        dp[m-1][n] = 1;
        //进行处理
        //0 -3 1
        //0  1 0
        for(int i = m - 1 ; i >= 0 ; i--)
        {
            for(int j = n - 1 ; j >= 0 ;j--)
            {
                dp[i][j] = min(dp[i+1][j] , dp[i][j+1]) - d[i][j];
                dp[i][j] = max(1 , dp[i][j]);//至少需要1滴血量
            }
        }
       
        return dp[0][0];
    }
};

4 简单多状态问题

4.1 买卖股票时机模型

买卖股票题单:

1. 309. 买卖股票的最佳时机含冷冻期
2. 714. 买卖股票的最佳时机含手续费
3. 123. 买卖股票的最佳时机 III
4. 188. 买卖股票的最佳时机 IV

这里以309. 买卖股票的最佳时机含冷冻期 为例：

首先我们通过题目可以知道，对于一天来说有三种状态：未持有股票，持有股票，冷冻期。而这三种状态是可以进行转换的。我们按照动态规划的解题方法进行解决：

1. 分析问题，确定dp表的意义：首先针对这道题来说，对于一天来说有三种状态，如果仅仅通过一个一维数组是不能解决问题的，那么就需要多个一维数组（二维数组）来解决。$dp[i]$表示该不同状态下该天可以获得的最大利润。

   • $dp[i][0]$表示未持有股票状态
   • $dp[i][1]$表示持有股票状态
   • $dp[i][2]$表示冷冻期状态

2. 推导状态转移方程，这个我们画图进行分析：
   

   • 未持有股票状态$dp[i][0]=max(dp[i-1][2],dp[i-1][0])$
   • 持有股票状态$dp[i][1]=max(dp[i-1][1],dp[i-1][0]-p[i])$
   • 冷冻期状态$dp[i][2]=dp[1][i-1]-p[i]$

3. 根据状态转移方程确定处理顺序：从左向右进行处理

4. 完成dp表的初始化问题：对第一天的进行处理即可，或者多扩展一位直接进行处理！

5. 进行处理

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //对于每一天来说有三种状态
        //买入 可交易 冷冻
        //0    1   2
        int n = prices.size();
        //建立dp表
        vector<vector<int>> dp(n ,  vector<int>(3));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        //进行处理
        for(int i = 1 ; i < n ; i++)
        {
            //该天之后是买入状态 
            dp[i][0] = max(dp[i-1][0] , dp[i-1][1] - prices[i]);
            //该天之后是“可交易”状态 
            dp[i][1] = max(dp[i-1][2] , dp[i-1][1]);
            //该天之后是“冷冻”状态
            dp[i][2] = dp[i-1][0] + prices[i];
        }
        return max(dp[n-1][1] , dp[n-1][2]);
    }
};

这样就成功解决了！

接下来我们来处理一道困难题：

首先我们通过题目可以知道，对于一天来说有两种状态：未持有股票，持有股票。这两种状态是可以进行转换的。并且买卖的次数是有限的！我们按照动态规划的解题方法进行解决：

1. 分析问题，确定dp表的意义：首先针对这道题来说，对于一天来说有两种状态，通过两个二维数组来解决。

   • $f[i][j]$表示该持有股票状态下第 i 天完成第 j 次交易 可以获得的最大利润。
   • $g[i][j]$表示该未持有股票状态下第 i 天完成第 j 次交易 可以获得的最大利润。

2. 推导状态转移方程，这个我们画图进行分析：
   

3. 根据状态转移方程确定处理顺序：从左向右进行处理，对每一天的所有交易状态进行处理

4. 完成dp表的初始化问题：对第一天的进行处理即可，第一天的所有交易状态都赋予一个极小值，方便后续处理

5. 进行处理

class Solution {
public:
    int maxProfit(int k, vector<int>& p) {
        //动态规划
        //首先分析状态情况
        //建表
        int n = p.size();
        vector<vector<int>> f(n , vector<int>(k+1 , 0));
        vector<vector<int>> g(n , vector<int>(k+1 , 0));
        //进行初始化
        f[0][0] = -p[0];
        //每个位置赋予一个极小值
        for(int i = 1 ; i < k+1 ; i++)
            f[0][i] =  -0x3f3f3f;
        g[0][0] = 0;
        for(int i = 1 ; i < k+1 ; i++)
            g[0][i] =  -0x3f3f3f;
        //进行处理
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j <= k ; j++)
            {
                f[i][j] = max(f[i-1][j] , g[i-1][j]-p[i]);
                g[i][j] = g[i-1][j];
                //只有 大于0次的交易次数才能进行该步操作 边界条件限制
                if(j-1 >=0) g[i][j] = max(g[i][j], f[i-1][j-1] + p[i]);
            }
        }

        //返回g的最后一列
        int ret = 0;
        for(int j = 0 ; j <= k ; j++)
        {
            ret = max(g[n-1][j] , ret);
        }
        return ret;
    
    }
};

这样就完成了！

4.2 打家劫舍模型

LCR 089. 打家劫舍
213. 打家劫舍 II

这里以213. 打家劫舍 II 为例

这里比较特殊的是房屋为环形结构！对于第一座房屋来说有两种情况：尾部房屋被偷，第一座不能偷；尾部房屋没被偷，第一座能偷。所以这里可以分解为两个动态规划问题进行解决！
我们按照动态规划的解题步骤进行解决：

1. 分析问题，确定dp表的意义：
   • $f[i]$第 i 个位置房屋被偷的最大金额
   • $g[i]$第 i 个位置房屋不被偷的最大金额
2. 推导状态转移方程
   • $f[i]=g[i-1]+nums[i]$
   • $g[i]=max(f[i-1],g[i-1])$
3. 根据状态转移方程确定处理顺序：从左向右处理
4. 完成dp表的初始化问题
5. 进行处理

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() <= 0) return 0;
        //动态规划解决问题
        //对于一个位置有两种选择 偷or不偷
        int n = nums.size();
        //         选择偷第一家                            不偷第一家
        return max(nums[0] + robhelper(nums , 2 , n-2) , robhelper(nums , 1 , n - 1));
    }
    //子问题解决
    int robhelper(vector<int>& nums , int left , int right)
    {
        if(left > right) return 0;
        int n = right - left + 1;
        vector<int> f(n , 0);//偷该家的最大金额
        vector<int> g(n , 0);//不偷该家的最大金额
        // 2 3
        // 0 2
        f[0] = nums[left];
        g[0] = 0;
        //对于第一个位置偷还是不偷有两种可能
        //偷第一个位置
        for(int i = 1 ; i < n ; i++)
        {
            //对于不偷此位置的情况：
            //[i-1]可以是偷或者不偷
            g[i] = max(f[i-1] , g[i-1]);
            //偷此位置那么前一个位置就不能选择
            f[i] = g[i-1] + nums[left + i];
        }

        return max(g[n-1] , f[n-1]);
    }
};

这样就解决了！

今天的动态规划问题就介绍到这里！
下一篇文章见！！！