C/C++ 算法入门：一维动态规划基础实战

源码

class Solution {
public:
    int tribonacci(int n) {
        // 1. 状态表示：dp[i] = 第 i 个泰波那契序列
        // 2. 状态转移方程：Tn+3 = Tn + Tn+1 + Tn+2 -> dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        vector<int> dp(n + 1);
        // 3. 初始化：需要前三个，那么就是初始化 0 1 2，从 3 开始
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        dp[0] = 0; dp[1] = 1; dp[2] = 1;
        // 4. 填表顺序：要求的值是 Ti，那么求就是 dp[i]，所以肯定是从小的开始，也就是从左往右
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        // 5. 返回值：dp[i] 即可
        return dp[n];
    }

    int tribonacci_optimized(int n) {
        // 空间优化写法
        int a = 0, b = 1, c = 1;
        int ret = 0;
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        for (int i = 3; i <= n; i++) {
            ret = a + b + c;
            a = b;
            b = c;
            c = ret;
        }
        return ret;
    }
};

2. 三步问题

题目

LeetCode: 三步问题

分析题目并提出解决方法

本题分析不难看出：要求到达某个台阶的方法（这里就能简单的看出来状态表示）。 直接拿示例一来看：如何到达台阶 n=3：

• 小孩每次可以走 1/2/3 步，那么那几个阶能到达呢？无非就是 n-1、n-2、n-3。
• 状态转移方程：dp[n] = dp[n-1] + dp[n-2] + dp[n-3]。
• 初始化：dp[0]=1、dp[1]=1、dp[2]=2。
• 移动方向：自然和上题一样从左往右，返回 dp[n] 即可。

题解核心逻辑

1. 状态表示：经验（以某个位置结尾/起始）+ 题目要求。
2. 状态转移方程：以 i 位置的状态，最近的一步，来划分问题。
   • dp[i] 分为三种情况：从 i-1、i-2、i-3 到达。
   • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
3. 初始化：dp[0]=1, dp[1]=1, dp[2]=2。
4. 填表顺序：从左往右。
5. 返回值：dp[n]。

注意取模运算防止溢出。

源码

class Solution {
public:
    int waysToStep(int n) {
        // 1. 状态表示：dp[n] 计算小孩上到 n 阶台阶有多少种上楼梯的方式
        // 2. 状态方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        vector<int> dp(n + 3);
        // 3. 初始值：同样的 0 1 2，但本题的初始化就没那么简单了
        dp[0] = 1; // 到达 0 阶有几种
        dp[1] = 1; // 到达 1 阶有几种
        dp[2] = 2; // 到达 2 阶有几种
        if (n <= 2) return dp[n];
        // 4. 方向：同样需要求 i 就得先找到 i-3... 那么就得从左往右
        for (int i = 3; i <= n; i++) {
            dp[i] = ((long)dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007;
        }
        // 5. 返回 dp[n] 即可
        return dp[n];
    }

    int waysToStep_optimized(int n) {
        // 空间优化写法
        if (n == 1 || n == 2) return n;
        if (n == 3) return 4;
        int dp1 = 1, dp2 = 2, dp3 = 4, dp4;
        for (int i = 4; i <= n; ++i) {
            dp4 = ((dp1 + dp2) % 1000000007 + dp3) % 1000000007;
            dp1 = dp2;
            dp2 = dp3;
            dp3 = dp4;
        }
        return dp4;
    }
};

3. 使用最小花费爬楼梯

题目

LeetCode: 使用最小花费爬楼梯

分析题目并提出解决方法

楼顶在最后。

题解核心逻辑

解法一：

1. 状态表示：dp[i] 表示：到达 i 位置时，最小花费。
2. 状态转移方程：
   • 先到达 i-1，然后支付 cost[i-1]，走一步：dp[i-1] + cost[i-1]。
   • 先到达 i-2，然后支付 cost[i-2]，走两步：dp[i-2] + cost[i-2]。
   • dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
3. 初始化：dp[0] = 0, dp[1] = 0（0 1 台阶是 0 元，所以直接从 2 开始即可）。
4. 填表顺序：由题意从左往右。
5. 返回值：dp[n]。

解法二：

1. 状态表示：dp[i]：从 i 位置开始，到达楼顶，此时的最小花费。
2. 状态转移方程：
   • 支付 cost[i]，往后走一步，从 i+1 位置出发到达终点：dp[i+1] + cost[i]。
   • 支付 cost[i]，往后走两步，从 i+2 位置出发到达终点：dp[i+2] + cost[i]。
   • dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])。
3. 初始化：dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]。
4. 填表顺序：从右往左。
5. 返回值：min(dp[0], dp[1])。

源码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用
        // 爬到楼顶本质就是超过容器个数 size=3 就需要爬到 4（下标 3）
        int n = cost.size();
        vector<int> dp(n + 1);
        // 2. 状态转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        // 3. 初始化：最小情况：dp[2] = min(dp[1], dp[0]) + cost[2]，故初始化 dp[1] dp[2] 即可
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1];
        }
        return dp[n];
    }
};

中断总结

1. 通过上述好几道题不难总结出常用的状态表示经验：
   • 以 i 位置为结尾，xxx
   • 以 i 位置为开始，xxx

通过上述三道题，估计你对动态规划中的最基本的步骤和思想都有一定的认识了，下面就不将是简单的套公式了，而是结合一些内容进一步深化对动态规划的理解。

4. 解码方法

题目

LeetCode: 解码方法

分析题目并提出解决方法

本题如何想到的呢：从最后一个节点来看，不难发现规律。

1. 要求第 i 位置的能否解码，就只用考虑：
   • 当前位置 i 是否符合（0 <= i <= 9）。
   • i 位置与 i-1 位置结合时是否符合 (10 <= i-1 + i <= 26)。
2. 要求总共的解码个数，则是通过 dp 表存储每个节点的解码个数，最小的情况是很容易推算的，所以使用动规中的 dp 表是能进行存储的。
3. 通过上面两个想法也就不难得出状态转移方程如何计算。

题解核心逻辑

1. 状态表示：以 i 结尾时，解法方法的总数。
2. 状态转移方程：
   • 分为两种情况：
     • dp[i] 单独解码（1 ~ 9）：解码成功（个数为 dp[i-1]），失败则为 0。
     • dp[i] 与 dp[i-1] 结合解码（10 ~ 26）：解码成功（dp[i-2]），失败则为 0。
3. 初始化：dp[0]、dp[1]。
4. 填表顺序：根据状态转移方程得知从左往右。
5. 返回值：dp[n-1]，n-1 最后一个位置。

优化：处理边界问题以及初始化问题的技巧

整个数组多开一位，然后通过使用这个多开的一位虚拟节点的初始化来帮助运算。 注意事项：

1. 虚拟节点的初始化是根据题目意思来的，保证后面填表的正确。一般来说填写 0，但本题对于该虚拟节点的使用，为了求原 dp 表中的 dp[1] 时使用的 dp[i-2]，所以填 1（因为前面也没字符判断了，所以填 1 给到 dp[2]，代表正确）。
2. 注意下标的映射关系，在真正使用 dp 时，因为 dp 表是多一格，对于 s 字符串中的下标要 -1：s[i-1]。

源码

class Solution {
public:
    int numDecodings(string s) {
        // dp[i]: 以 i 位置结尾的解码个数
        // dp[i] = dp[i-1] + dp[i-2]，其中若不能解码则不进行相加，或者加 0
        // 初始化：因为 s.length >= 1，所以需要一个多的空位，来特殊处理等于 1 的情况
        int n = s.size();
        vector<int> dp(n + 2);
        // 结果存在 n 下标
        dp[0] = 1; // 默认解码个数为 1 次
        dp[1] = 1; // 默认解码个数为 1 次
        if (s[0] == '0') return 0;
        
        for (int i = 0; i < n; i++) {
            // 单个字符判断
            int val = s[i] - '0';
            if (val >= 1 && val <= 9) dp[i + 2] += dp[i + 1];
            
            // 两个字符判断
            int combine = i - 1 >= 0 ? (s[i - 1] - '0') * 10 + val : -1;
            if (combine >= 10 && combine <= 26) dp[i + 2] += dp[i];
        }
        return dp[n + 1];
    }
};

对于需要判断两位或者多位数字时，不要图方便使用字符判断，而是将他转换为数字。