计数型问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

动态规划的本质：它是一种 “以空间换时间”的优化算法，核心是把复杂问题拆解为多个重叠的子问题，通过记录子问题的最优解（状态），避免重复计算，最终由子问题的最优解推导出原问题的最优解。

算法回顾

动态规划的适用有三个核心前提（缺一不可），这也是判断一个问题是否能用 DP 解决的关键：
- 最优子结构：原问题的最优解包含其子问题的最优解；
- 重叠子问题：求解原问题时，会反复遇到相同的子问题（这是 DP 能优化的基础，否则不如暴力递归）；
- 无后效性：某一阶段的状态确定后，后续的状态推导只依赖当前状态，与状态的形成过程无关。

计数型问题

计数型问题是求解决问题的所有合法方案数，比如 “有多少种方法到达终点”“有多少种组合满足条件”。这类问题同样存在重叠子问题，DP 通过记录 “到达某一状态的方案数”，由子状态的方案数累加得到当前状态的方案数，本质是 “最优子结构” 的延伸（方案数的累加性）。

核心解题思路
- 定义状态：dp[i]/dp[i][j]表示 “到达第 i 个状态 / 位置 (i,j) 的合法方案数”；
- 初始状态：边界位置的方案数初始化（如起点dp[0][0] = 1，表示只有 1 种方法到起点）；
- 状态转移方程：当前状态的方案数 = 所有能到达当前状态的子状态方案数之和（如dp[i] = dp[i-1] + dp[i-2]）；
- 结果：dp[目标状态]即为总方案数。

典型例题
- 不同路径（LeetCode 62）：网格中从左上到右下，只能右 / 下走，求路径数（二维 DP）；
- 不同路径 II（LeetCode 63）：网格中有障碍，求合法路径数（二维 DP，加约束判断）；
- 整数拆分（LeetCode 343）：将 n 拆分为至少两个正整数的和，求乘积最大的拆分方式数（一维 DP）；
- 解码方法（LeetCode 91）：将数字字符串解码为字母（1->A，26->Z），求合法解码数（一维 DP）。

教程目录导航

▼

计数型问题

一、不同路径（LeetCode 62）

问题描述：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
- 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
- 问总共有多少条不同的路径？
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 10⁹
示例 1：
- 输入：m = 3, n = 7
- 输出：28
示例 2：
- 输入：m = 3, n = 2
- 输出：3
- 解释：
  - 从左上角开始，总共有 3 条路径可以到达右下角。
  - 1. 向右 -> 向下 -> 向下
  - 2. 向下 -> 向下 -> 向右
  - 3. 向下 -> 向右 -> 向下

算法解析：

确定状态：定义 dp[i][j] 表示：从网格左上角 (0,0) 走到位置 (i,j) 的不同路径数。
状态转移方程：
- 边界情况：
  - 第一行（i=0, j>0）：只能从左边来 → dp[0][j] = 1；
  - 第一列（j=0, i>0）：只能从上面来 → dp[i][0] = 1。
- 通用情况（i>0, j>0）：
  - 到达 (i,j) 的路径数 = 到达上方 (i-1,j) 的路径数 + 到达左方 (i,j-1) 的路径数 → dp[i][j] = dp[i-1][j] + dp[i][j-1]。
初始化：
- dp[0][0] = 1（起点只有 1 种路径：原地不动）；
- 第一行、第一列全部初始化为 1（路径唯一）。
遍历顺序：从左到右（i 从 1 到 m，j 从 1 到 n）。
最终 dp[m-1][n-1] 就是从左上角到右下角的不同路径总数。

dp 数组计算过程：

输入：m = 3, n = 7

初始化 DP 数组：第一行全部为 1，第一列全部为 1
填充非边界位置：
- i=1
  - j=1：dp[0][1] + dp[1][0] = 1 + 1 = 2 → dp[1][1] = 2
  - j=2：dp[0][2] + dp[1][1] = 1 + 2 = 3 → dp[1][2] = 3
  - j=3：dp[0][3] + dp[1][2] = 1 + 3 = 4 → dp[1][3] = 4
  - j=4：dp[0][4] + dp[1][3] = 1 + 4 = 5 → dp[1][4] = 5
  - j=5：dp[0][5] + dp[1][4] = 1 + 5 = 6 → dp[1][5] = 6
  - j=6：dp[0][6] + dp[1][5] = 1 + 6 = 7 → dp[1][6] = 7
- i=2
  - j=1：dp[1][1] + dp[2][0] = 2 + 1 = 3 → dp[2][1] = 2
  - j=2：dp[1][2] + dp[2][1] = 3 + 3 = 6 → dp[2][2] = 6
  - j=3：dp[1][3] + dp[2][2] = 4 + 6 = 10 → dp[2][3] = 10
  - j=4：dp[1][4] + dp[2][3] = 5 + 10 = 15 → dp[2][4] = 15
  - j=5：dp[1][5] + dp[2][4] = 6 + 15 = 21 → dp[2][5] = 21
  - j=6：dp[1][6] + dp[2][5] = 7 + 21 = 28 → dp[2][6] = 28


#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    // 定义二维DP数组，dp[i][j]表示从(0,0)到(i,j)的路径数
    vector<vector<int>> dp(m, vector<int>(n));

    // 填充第一列
    for (int i = 0; i < m; ++i) {
        dp[i][0] = 1;
    }
    // 填充第一行
    for (int j = 0; j < n; ++j) {
        dp[0][j] = 1;
    }

    // 填充非边界位置（i>0且j>0）
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

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

int main() {
    cout << "m=3, n=7: " << uniquePaths(3, 7) << endl; // 输出 28
    cout << "m=3, n=2: " << uniquePaths(3, 2) << endl; // 输出 3
    cout << "m=7, n=3: " << uniquePaths(7, 3) << endl; // 输出 28

    return 0;
}

输出结果


m=3, n=7: 28
m=3, n=2: 3
m=7, n=3: 28

二、不同路径 II（LeetCode 63）

问题描述：

给定一个 m x n 的整数数组 grid。一个机器人初始位于左上角（即 grid[0][0]）。机器人尝试移动到右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。。
- 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。
- 返回机器人能够到达右下角的不同路径数量。
- 测试用例保证答案小于等于 2 * 10⁹。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- grid[i][j] 为 0 或 1
示例 1：
- 输入：grid = [[0,0,0],[0,1,0],[0,0,0]]
- 输出：2
- 解释：3x3 网格的正中间有一个障碍物。
- 从左上角到右下角一共有 2 条不同的路径：
  - 1. 向右 -> 向右 -> 向下 -> 向下
  - 2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
- 输入：grid = [[0,1],[0,0]]
- 输出：1

算法解析：

确定状态：定义 dp[i][j] 表示：从 (0,0) 走到 (i,j) 的有效路径数（若 (i,j) 是障碍物，则 dp[i][j] = 0）。
状态转移方程：
- 边界情况：
  - 第一行（i=0, j>0）：只能从左边来 → 若 grid[0][j] != 1，则 dp[0][j] = dp[0][j-1]（否则为 0）；
  - 第一列（j=0, i>0）：只能从上面来 → 若 grid[i][0] != 1，则 dp[i][0] = dp[i-1][0]（否则为 0）；
- 通用情况（i>0, j>0 且无障碍物）：
  - dp[i][j] = dp[i-1][j] + dp[i][j-1]（和 62 题一致，仅累加有效路径数）。
初始化：
- 起点初始化：若 grid[0][0] == 1（起点有障碍物），直接返回 0；否则 dp[0][0] = 1；
- 第一行 / 第一列初始化时，需逐个判断是否有障碍物，一旦遇到障碍物，后续位置路径数均为 0（无法绕过）。
遍历顺序：从左到右（i 从 1 到 m，j 从 1 到 n）。
最终 dp[m-1][n-1] 即为答案（若终点是障碍物，结果为 0）。

dp 数组计算过程：

输入：grid = [[0,0,0],[0,1,0],[0,0,0]]

初始化 DP 数组：dp[0][0] = 1
填充第一行
- j=1：无障碍物 + dp [0][0]=1 → dp [0][1] = 1；
- j=2：无障碍物 + dp [0][1]=1 → dp [0][2] = 1；
- 第一行 DP 结果：[1,1,1]
填充第一列
- i=1：无障碍物 + dp [0][0]=1 → dp [1][0] = 1；
- i=2：无障碍物 + dp [1][0]=1 → dp [2][0] = 1；
- 第一列 DP 结果：[1,1,1]
填充非边界位置：
- i=1
  - j=1：有障碍物 → dp[1][1] = 0
  - j=2：无障碍物 → dp[0][2] + dp[1][1] = 1 + 0 = 1 → dp[1][2] = 1
- i=2
  - j=1：无障碍物 → dp[1][1] + dp[2][0] = 0 + 1 = 2 → dp[2][1] = 1
  - j=2：无障碍物 → dp[1][2] + dp[2][1] = 1 + 1 = 2 → dp[2][2] = 2


#include <iostream>
#include <vector>
using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;

    int m = obstacleGrid.size();    // 行数
    int n = obstacleGrid[0].size(); // 列数

    // 起点有障碍物，直接返回0
    if (obstacleGrid[0][0] == 1) return 0;

    // 定义DP数组，dp[i][j]表示从(0,0)到(i,j)的有效路径数
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = 1; // 初始化起点

    // 填充第一行（只能从左边来）
    for (int j = 1; j < n; ++j) {
        // 无障碍物 且 左边位置可达 → 路径数=左边路径数；否则为0
        if (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) {
            dp[0][j] = 1;
        }
    }

    // 填充第一列（只能从上面来）
    for (int i = 1; i < m; ++i) {
        // 无障碍物 且 上边位置可达 → 路径数=上边路径数；否则为0
        if (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) {
            dp[i][0] = 1;
        }
    }

    // 填充其余位置
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            // 有障碍物 → 路径数为0
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                // 无障碍物 → 路径数=上边+左边
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

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

int main() {
    // 测试用例1：输出 2
    vector<vector<int>> grid1 = {{0,0,0},{0,1,0},{0,0,0}};
    cout << "Test Case 1: " << uniquePathsWithObstacles(grid1) << endl;

    // 测试用例2：输出 0（终点有障碍物）
    vector<vector<int>> grid2 = {{0,0},{1,1},{0,0}};
    cout << "Test Case 2: " << uniquePathsWithObstacles(grid2) << endl;

    // 测试用例3：输出 1（单行无障碍物）
    vector<vector<int>> grid3 = {{0,0,0,0}};
    cout << "Test Case 3: " << uniquePathsWithObstacles(grid3) << endl;

    return 0;
}

输出结果


Test Case 1: 2
Test Case 2: 0
Test Case 3: 1

三、整数拆分（LeetCode 343）

问题描述：

给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。
- 返回你可以获得的最大乘积。
提示：
- 2 <= n <= 58
示例 1：
- 输入: n = 2
- 输出: 1
- 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2：
- 输入: n = 10
- 输出: 36
- 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

算法解析：

确定状态：定义 dp[i] 为将整数 i 拆分后能得到的最大乘积；
状态转移方程：
- 不继续拆分 j：乘积为 j × (i-j)；
- 继续拆分 j：乘积为 j × dp[i-j]；
- 取两者的最大值作为 dp[i] 的候选值；
初始化：dp[2] = 1（2 只能拆成 1+1）。
遍历顺序：从左到右（i 从 3 到 n）。
最终 dp[n] 即为 n 拆分后的最大乘积。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int integerBreak(int n) {
    // dp[i] 表示拆分整数i能得到的最大乘积
    vector<int> dp(n + 1, 0);
    // 初始条件：2只能拆成1+1，乘积为1
    dp[2] = 1;

    // 从3开始计算每个数的最大乘积
    for (int i = 3; i <= n; ++i) {
        // 遍历所有可能的拆分点j（1 <= j < i）
        for (int j = 1; j < i; ++j) {
            // 两种情况：j*(i-j)（不拆i-j） 或 j*dp[i-j]（拆i-j）
            int current = max(j * (i - j), j * dp[i - j]);
            // 更新dp[i]为所有可能中的最大值
            dp[i] = max(dp[i], current);
        }
    }

    return dp[n];
}

int main() {
    int n1 = 2, n2 = 10;
    cout << "n = " << n1 << " 时，最大乘积：" << integerBreak(n1) << endl; // 输出1
    cout << "n = " << n2 << " 时，最大乘积：" << integerBreak(n2) << endl; // 输出36

    return 0;
}

输出结果


n = 2 时，最大乘积：1
n = 10 时，最大乘积：36

四、解码方法（LeetCode 91）

问题描述：

一条包含字母 A-Z 的消息通过以下映射进行了编码："1" -> 'A'、"2" -> 'B'、"3" -> 'C'、......、"26" -> 'Z'
给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回 0。
- 然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。
- 例如，"11106" 可以映射为：
- "AAJF" ，将消息分组为 (1, 1, 10, 6)
- "KJF" ，将消息分组为 (11, 10, 6)
- 消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。
提示：
- 注意，可能存在无法解码的字符串。
- 1 <= s.length <= 100
- s 只包含数字，并且可能包含前导零。
示例 1：
- 输入：s = "12"
- 输出：2
- 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
- 输入：s = "226"
- 输出：3
- 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
- 输入：s = "06"
- 输出：0
- 解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

算法解析：

确定状态：定义 dp[i] 表示字符串前 i 个字符的解码方式总数；
状态转移方程：
- 单字符解码：如果 s[i-1] != '0'，则 dp[i] += dp[i-1]；
- 双字符解码：如果 s[i-2] 和 s[i-1] 组成的数字在 10-26 之间，则 dp[i] += dp[i-2]。
初始化：
- dp[0] = 1（空字符串有 1 种解码方式，作为边界条件）；
- dp[1] = s[0] == '0' ? 0 : 1（第一个字符非 0 则 1 种，否则 0 种）；
遍历顺序：从左到右（i 从 2 到 n）。
最终 dp[n] 即为 s 解码方法的总数。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int numDecodings(string s) {
    int n = s.size();
    // 空字符串或首字符为0，直接返回0
    if (n == 0 || s[0] == '0') return 0;

    // dp[i] 表示前i个字符的解码方式数
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // 边界条件：空字符串有1种解码方式
    dp[1] = 1; // 第一个字符非0，初始为1

    for (int i = 2; i <= n; ++i) {
        // 情况1：单独解码第i个字符（对应s[i-1]）
        if (s[i-1] != '0') {
            dp[i] += dp[i-1];
        }

        // 情况2：解码第i-1和i个字符组成的两位数（对应s[i-2]和s[i-1]）
        int two_digit = stoi(s.substr(i-2, 2)); // 提取两位数字
        if (two_digit >= 10 && two_digit <= 26) {
            dp[i] += dp[i-2];
        }
    }

    return dp[n];
}

int main() {
    cout << numDecodings("12") << endl;   // 输出2
    cout << numDecodings("226") << endl;  // 输出3
    cout << numDecodings("06") << endl;   // 输出0
    cout << numDecodings("10") << endl;   // 输出1（只有10一种方式）

    return 0;
}

输出结果

返回顶部