算法——动态规划

1. 什么是动态规划？

动态规划（Dynamic Programming）是一种解决多阶段决策问题的优化方法。它通常用于解决具有重叠子问题和最优子结构性质的问题，能够将一个大问题分解为多个重叠的子问题，并通过存储子问题的解来避免重复计算，从而提高算法效率。

动态规划的基本思想是将原问题分解为若干子问题，先求解子问题的解，然后将这些子问题的解组合起来，逐步推导出原问题的解。为了避免重复计算，动态规划算法通常采用表格（数组）来存储已经求解的子问题的解，这种表格通常称为动态规划(dp)表。 

2. 动态规划算法的解题流程

动态规划算法的一般步骤如下：

1. 定义状态： 明确定义问题的状态，将原问题转化为具有重叠子问题的子问题。在解题中体现为确认dp表中每一个格子表示什么。

2. 找到状态转移方程： 建立子问题之间的递推关系，通过状态转移方程描述问题的最优子结构。在解题中体现为dp表如何去填写。

3. 初始化： 初始化动态规划表，将边界状态的值填入表中。在解题中，初始化的目的是为了保证最后得到的结果是正确的。

4. 逐步计算： 从边界状态开始，按照状态转移方程逐步计算并填充动态规划表。在解题中，体现为确认填dp表的方向。

5. 解读结果： 根据动态规划表中的结果得到原问题的解。在解题中，体现为返回正确结果。

3. 应用实例

①斐波那契数列模型

1. 第N个泰波那契数

题目链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）

解析：看完这道题，我们分析这个题目可以发现，题目已经将几乎动态规划的所有步骤告诉了我们，我们只需要按照他说的完成流程即可，我们定义dp[i]表示第i个泰波那契数，我们的动态转移方程为 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，而初始化要想得到正确结果，我们需要将dp[0] = 0, dp[1] = dp[2] = 1，填表方向则是从左向右从第3个位置开始填，最后返回dp[n]即可（n为0,1,2时需要进行特殊判断），代码如下

class Solution 
{
public:
    int tribonacci(int n) 
    {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        vector<int> dp(n+1);
        dp[1] = dp[2] = 1;

        for (int i = 3; i <= n; i++)
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

        return dp[n];
    }
};

2. 三步问题

题目链接：面试题 08.01. 三步问题 - 力扣（LeetCode）

解析：分析这个题目，我们可以创建一个大小为(n+1)的dp表，我们定义dp[i]为到小孩上到第i个阶梯共有多少种方式，根据题目我们可以发现，要想到达dp[i]这个位置，我们有三种方法上来，分别是从前三个位置上来，即

所以我们可以得到dp[i]的动态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，初始化时，只有前三个台阶需要特殊处理，由于一开始就处于第0个台阶因此dp[0]=1，到第一个台阶只有一种方法，所以dp[1] = 1，到第二个台阶有2种方法，所以dp[2] = 2，由于题目中是从下往上跳，因此填表顺序为从第三个台阶开始从左向右填，最终返回dp[n]即可，代码如下

class Solution 
{
public:
    int waysToStep(int n) 
    {
        if (n <= 1) return 1;
        if (n == 2) return 2;

        int mod = 1e9 + 7;
        vector<long long> dp(n+1);
        dp[0] = dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % mod;
        
        return dp[n];
    }
};

3. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）

解析：分析题目，我们可以定义dp[i]表示到第i个阶梯的最小花费，而要想到达第i个阶梯，要么只能从第i-1个阶梯来，要么只能从i-2个阶梯来，我们只需要最小的花费，所以动态转移方程如下 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);，由于可以选择下标从0或1的阶梯开始爬，因此我们无需初始化，填表顺序为从前往后填，最后返回dp[n]即可，代码如下

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        vector<int> dp(n+1);

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

除了从左向右填表外，我们还可以从右向左填表，定义dp[i]表示从第i个阶梯开始到达楼顶的最小花费，从第i个阶梯向后移动，要么只能移动一步要么只能移动两步，我们需要得到其中较小的一种情况，因此有 dp[i] = min(dp[i+1], dp[i+2]) + cost[i]，由于从倒数第一和倒数第二个阶梯都能直接到达楼顶，因此我们需要初始化dp[n-1] = cost[n-1], dp[n-2] = cost[n-2], 填表时从后往前填即可，最终返回dp[0]与dp[1]中的较小值，代码如下

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        vector<int> dp(n+1);
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];

        for(int i = n - 3; i >= 0; i--)
            dp[i] = min(dp[i+1], dp[i+2]) + cost[i];

        return min(dp[0], dp[1]);
    }
};

4. 解码方法

题目链接：91. 解码方法 - 力扣（LeetCode）

解析：分析这个题目，我们可以定义dp[i]表示到达第i个字符时共有多少种解码方法，若当前单个字符能够解码（不为'0'），则表明当前字符是一种解码方法，此时判断当前字符是否能和前一个字符共同解码，若能就可以使dp[i]+1，否则不变；若当前字符不能够解码（为'0'），则表明当前字符不是一种解码方式，此时判断当前字符是否能和前一个字符共同解码，若能就使dp[i]-1，否则dp[i]就置为0，对于初始化我们只需要知道第一个字符是否为'0'即可，是的话dp[0] = 0，不是的话dp[0] = 1，填表顺序为从左往右填，最终返回dp[n-1]即可，代码如下

class Solution 
{
public:
    int numDecodings(string s) 
    {
        int n = s.size();
        vector<int> dp(n);
        if (s[0] != '0') dp[0] = 1;

        for (int i = 1; i < n; i++)
        {
            int code = stoi(s.substr(i-1, 2));
            if (s[i] != '0')
            {
                if (code >= 10 && code <= 26) dp[i] = dp[i-1] + 1;
                else dp[i] = dp[i-1];
            }
            else
            {
                if (code >= 10 && code <= 26) dp[i] = dp[i-1] - 1;
                else dp[i] = 0;
            }
        }

        return dp[n-1];
    }
};