动态规划（一）——思想入门

前置知识

在正式开始动态规划的题目练习之前，我们来看看动态规划的一般步骤。

一般步骤：

1. 状态表示：创建一个 dp 表，确定 dp[i] 的含义。通常结合经验与题目要求得出。
2. 状态转移方程：推导 dp[i] 等于什么，如何由之前的状态得到当前状态。
3. 初始化：保证填表时不越界。
4. 填表顺序：确保计算当前状态所需的前置状态已计算完成。
5. 返回结果：根据题目要求和状态表示返回最终结果。

接下来结合具体题目进行说明。

第 N 个泰波那契数

第 N 个泰波那契数

该题类似于斐波那契数列，但当前数是前三数之和。

1. 状态表示：dp[i] 表示当前位置的泰波那契数。
2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
3. 初始化：当 i=1 时会出现越界，需初始化。根据题目：dp[0]=0, dp[1]=1, dp[2]=1。
4. 填表顺序：从前向后依次推出后面。
5. 返回结果：直接返回 dp[n]。

边界情况处理：n 的范围是 0~37，当 n=0, 1, 2 时直接返回对应值。

class Solution {
public:
    int tribonacci(int n) {
        // 1、创建 dp 表
        vector<int> dp(n+1);
        // 处理边界情况
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        // 2、初始化——避免越界
        dp[0]=0, dp[1]=1, dp[2]=1;
        // 3、根据状态转移方程填表
        for(int i=3; i<=n; i++) {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        // 4、返回结果
        return dp[n];
    }
};

算法复杂度：时间复杂度 O(N)，空间复杂度 O(N)。

优化解法：使用滚动数组将空间复杂度优化为 O(1)。

class Solution {
public:
    int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int a=0, b=1, c=1;
        int d=0;
        int count=n-2;
        while(count--) {
            d=a+b+c;
            a=b;
            b=c;
            c=d;
        }
        return d;
    }
};

使用最小花费爬楼梯

使用最小花费爬楼梯

注意点：楼顶不是最后一个下标的位置，而是最后一个下标后面的位置。

状态表示方法一

1. 状态表示：dp[i] 是以 i 位置为结尾的最小花费。
2. 状态转移方程：到达 i 位置可能从 i-1 或 i-2 过来。dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。
3. 初始化：可以从下标 0 或 1 开始，故 dp[0]=0, dp[1]=0。
4. 填表顺序：从前向后。
5. 返回结果：返回 dp[n]。

代码实现：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n+1, 0);
        // dp[0], dp[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];
    }
};

状态表示方法二

1. 状态表示：dp[i] 是以 i 位置为起点到达楼顶的最小花费。
2. 状态转移方程：从 i 出发走一步到 i+1 或两步到 i+2。dp[i] = min(dp[i+1]+cost[i], dp[i+2]+cost[i])。
3. 初始化：i=n-1 时往上走一步花费 cost[n-1]，i=n 时在楼顶花费 0。即 dp[n-1]=cost[n-1], dp[n]=0。
4. 填表顺序：从后向前。
5. 返回结果：起点可能是 0 或 1，返回 min(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]=0;
        for(int i=n-2; i>=0; i--) {
            dp[i]=min(dp[i+1]+cost[i], dp[i+2]+cost[i]);
        }
        return min(dp[0], dp[1]);
    }
};

解码方法

解码方法

常规解法

AZ 对应 126，0 无法单独解码，前置 0 也无法解码。分为单独解码和组合解码两种情况。

1. 状态表示：dp[i] 是以 i 位置为结尾的解码方式种数。
2. 状态转移方程：
   • 若 s[i] 可单独解码，dp[i] += dp[i-1]。
   • 若 s[i-1] 和 s[i] 可组合解码（10~26），dp[i] += dp[i-2]。
3. 初始化：
   • dp[0]：s[0] 不为 '0' 则为 1，否则为 0。
   • dp[1]：根据 s[1] 是否可单独及 s[0..1] 是否可组合判断。
4. 填表顺序：从前向后。
5. 返回结果：返回 dp[n-1]。

代码实现：

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

优化解法

通过多开辟一个空间，将初始化代码写入循环中，简化边界处理。

1. 多开空间含义：dp[0] 设为 1，用于辅助计算前两个字符的组合情况。
2. 下标映射：dp[i] 对应字符串 s 的第 i-1 个字符。

代码实现：

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