推荐|基础dp——动态规划

用动规解题过程中，在找子问题时我总结了一个很厉害的小技巧，就是保留主问题的逻辑，而换一个问题的对象。比如这里，主问题是从起点爬到楼顶的最小花费，那么构造子问题时我们只需要保留这个问题的逻辑，而把楼顶这个对象改成任意位置i。那么我们就得到了一个子问题（即从起点爬到i位置的最小花费）。然后我们再假设前面的相同的子问题已经解决。

比如：

动规题复杂多变，以上技巧可以解决大部分的基础动规题，但更多的只是作为一个小经验，并不是所有动规题都可以通过构建子问题来解决的。

在解一个题时，状态表示可以是很多，不同的状态表示就决定了不同的状态转移方程，而要判断一个状态表示是否正确只需看是否能根据该状态表示推出正确的状态转移方程。

能够理解上图那么动态规划的五步骤就水到渠成了。

状态表示： dp[i]：表示爬到i时的最小花费
状态转移方程： dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
初始化： dp表初始化为全0
填表顺序： 从下标为2的位置开始，并且从左往右填写
返回值： return dp[n]

代码示例：


class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost){
        int n=cost.size();
        vector<int> dp(n+1);//默认值就是0，不用初始化
        for(int i=2;i<=n;i++) 
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        return dp[n];    
    }
};

除了刚才的状态表示我们还可以换一个，只需要改变一下子问题，同样的技巧，主问题逻辑不变，把起点这个对象改成任意位置i，那么我们就得到了一个子问题（即从i位置爬到楼顶的最小花费）。

状态表示： dp[i]：表示从i爬到楼顶的最小花费
状态转移方程： dp[i]=cost[i]+min(dp[i+1],dp[i+2])
初始化： dp[n-1]=cost[n-1]，dp[n-2]=cost[n-2]
填表顺序： 从右往左
返回值： return min(dp[0], dp[1])

我们可以发现状态表示的改变使得其他四个步骤的实现逻辑改变，所以可见状态表示的重要性。

代码示例：


class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost){
        int n=cost.size();
        vector<int> dp(n);
        dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
        for(int i=n-3;i>=0;i--) 
            dp[i]=cost[i]+min(dp[i+1],dp[i+2]);
        return min(dp[0],dp[1]);    
    }
};

提示：空间优化：在我们填写某一个状态的时候只需要使用它的前两个状态，所以可以把dp数组简化为两个变量就可以解决问题（需要注意变量的更新）。通常把该优化方法叫做“滚动数组”。很多基础动规都可以进行这样的优化，大家可以试着去实现，这一点在后面也不再提。

提示：为了减少逻辑上的赘述，在以下题解中我都只会讲解一种状态表示作为示例。

2.下降路径最小和

通过上一题找子问题的经验，我们可以这样做：

抓住主问题：从第一行任意位置下降到最后一行的任意一个位置的最小和。

保留问题的主逻辑，把对象“第一行任意位置”或“最后一行任意位置”更改，比如更改“最后一行任意位置”为“第i行的任意位置j”。得到子问题，即从“第一行任意位置下降到第i行的任意位置j的最小和”。

接下来假设与它相同的子问题都解决，并利用它们的结果。如下：

动规五步骤：

状态表示： dp[i][j]：从第一行任意位置下降到第i行j列的最小和
状态转移方程： dp[i][j]=matrix[i][j]+min(dp[i-1][j-1]，min(dp[i-1][j]，dp[i-1][j+1]) )
初始化：越界区域如下：

创建(n+1)*(n+2)的dp表初始化为全INT_MAX（这样创建dp表减少了为防止越界而做特殊判断带来的成本）,再将第一行初始化为全0。把dp表初始化为全INT_MAX，是为了防止越界区域参与最小值的筛选。再把第一行初始化为全0是逻辑需要，总的目的都是为了保证填表的正确性。

填表顺序： 从上到下，从左往右（或从右往左，只要能保证在填写当前状态时需要的状态已计算过即可）
返回值： 返回最后一行的最小值

代码示例：


class Solution {
public:
    int minFallingPathSum(vectorint>>& matrix)
    {
        int n=matrix.size();//题目明确指出是方形，所以行数和列数都一样。
        vectorint>> dp(n+1,vector<int>(n+2,INT_MAX));
        for(int j=0;j2;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=matrix[i-1][j-1]+min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]);
        int ret=INT_MAX;
        for(int j=1;j<=n;j++) ret=min(ret,dp[n][j]);
        return ret;
    }
};

3.解码方法

主问题：一个非空字符s的解码方法的总数。但我们好像无法从中获取到可以更改的对象，再回去观察上面我们解决的两道问题。它们主问题的逻辑中都是带有区间式的，比如第一题：从起点到终点，第二题：从第一行到最后一行。那么如果我们还想要那个找子问题的技巧去确定状态表示，那么在总结主问题时就要朝着带有区间式的方向去想。

这里我们可以把主问题总结为：从s字符串的下标0开始到下标n-1结束的解码方法总数。那么这样我们就构造出了一个区间“开始”——“结束”。子问题就好构建得多了。

子问题：从下标0开始到下标i结束的解码方法总数。

状态表示： dp[i]：表示从下标0开始到下标i结束的解码方法总数
状态转移方程：

解决了状态表示但这个题的难点主要在于状态转移方程。

我们可以把单独解码与和前一个联合解码分开讨论。如果单独解码成功相当于在i-1的所有解码方法中统一加上一个s[i]，所以为dp[i-1]，解码失败的话，说明不能单独解码，所以结果为0。

        同理联合解码成功相当于在i-2的所有解码方法中统一加上一个s[i]与s[i-1]的复合，所以为dp[i-2]，解码失败的话，说明不能联合解码所以结果为0。最后只需要把单独解码与联合解码的结果相加。

初始化：因为我们在用dp[i]时需要用到dp[i-1]和dp[i-2]的状态，所以最好把dp[0]和dp[1]初始化。dp[0]可以这样写dp[0]=s[i]!='0'，但dp[1]的初始化会比较麻烦，它的初始化逻辑和上面的状态转移方程是一样的。而在下面填表时同样要用到这样的逻辑，就会显得很累赘。

        我们可以使用这样一个初始化技巧：

        那么可以做一个n+1大小的dp表，然后错开一位表示，即 dp[i]：表示从下标0开始到下标i-1结束的解码方法总数。为保证后面的填表顺序正确我们需要dp[1]=s[i]!='0'，这是必然的。而dp[0]该初始化为什么？我们可以思考什么时候用到dp[0]，即s[0]与s[1]解码成功时，那么它必然是dp[0]=1

填表顺序：从dp的2下标开始，并从左往右。
返回值： return dp[n]

代码示例：


class Solution {
public:
    int numDecodings(string s)
    {
        vector<int> dp(s.size()+1,0);
        dp[1]=s[0]!='0',dp[0]=1;
        for(int i=2;isize();i++)
        {
            int m=(s[i-2]-'0')*10+s[i-1]-'0';
            if(s[i-1]!='0') dp[i]+=dp[i-1];
            if(m>=10&&m<=26) dp[i]+=dp[i-2];
        }
        return dp.back();
    }
};

非常感谢您能耐心读完这篇文章。倘若您从中有所收获，还望多多支持呀！

一、什么是动态规划？

二、动态规划的使用步骤

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

三、试题讲解

1.最小花费爬楼梯

2.下降路径最小和

3.解码方法

评论记录：