91.解码方法（中等）★★★☆☆

2021有赞笔试题第一题

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size(); // 获取字符串的长度
        vector<int> dp(n); // 动态规划数组，dp[i] 表示前 i 个字符的解码方法数

        // 如果第一个字符是 '0'，则无法解码
        if ((s[0] - '0') == 0) {
            return 0;
        }

        // 如果字符串长度为 1，只有一个解码方法
        if (n == 1) {
            return 1;
        }

        // 初始化 dp 数组
        dp[0] = 1; // 第一个字符的解码方法数为 1

        // 处理前两个字符
        if ((s[0] - '0') * 10 + (s[1] - '0') <= 26 && (s[1] - '0') != 0) {
            // 如果前两个字符组成的数字在 10 到 26 之间，且第二个字符不是 '0'，则有两种解码方法
            dp[1] = 2;
        } else if ((s[1] - '0') == 0 && (s[0] - '0') * 10 + (s[1] - '0') > 26) {
            // 如果第二个字符是 '0'，且前两个字符组成的数字大于 26，则无法解码
            return 0;
        } else {
            // 否则，只有一个解码方法
            dp[1] = 1;
        }

        // 从第三个字符开始，逐个处理
        for (int i = 2; i < n; ++i) {
            int x = 0; // 用于存储当前字符和前一个字符组成的数字的解码方法数
            int y = 0; // 用于存储当前字符单独的解码方法数

            // 检查当前字符和前一个字符组成的数字是否在 10 到 26 之间
            if ((s[i - 1] - '0') * 10 + (s[i] - '0') <= 26 && (s[i - 1] - '0') * 10 + (s[i] - '0') >= 10) {
                x = dp[i - 2]; // 如果在范围内，则解码方法数等于 dp[i-2]
            }

            // 检查当前字符是否不是 '0'
            if ((s[i] - '0') != 0) {
                y = dp[i - 1]; // 如果不是 '0'，则解码方法数等于 dp[i-1]
            }

            // 当前字符的解码方法数等于 x 和 y 的和
            dp[i] = x + y;
        }

        // 返回整个字符串的解码方法数
        return dp[n - 1];
    }
};

---

62.不同路径（极简）★☆☆☆☆

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 创建一个二维动态规划数组 dp，大小为 m x n
        // 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;
        }

        // 填充 dp 数组的其余部分
        // 对于每个点 (i,j)，到达该点的路径数等于从左边来和从上边来的路径数之和
        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];
            }
        }

        // 返回从起点到终点 (m-1, n-1) 的唯一路径数
        return dp[m - 1][n - 1];
    }
};

---

931. 下降路径最小和（极简）★☆☆☆☆

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size(); // 获取矩阵的行数
        int m = matrix[0].size(); // 获取矩阵的列数
        // 创建一个动态规划数组 dp，大小为 (n+1) x (m+2)，初始化为 INT_MAX
        // dp[i][j] 表示到达第 i 行第 j 列的最小下降路径和
        vector<vector<int>> dp(n + 1, vector<int>(m + 2, INT_MAX));
        
        // 初始化 dp 的第一行，所有值设为 0
        // 这是因为从虚拟的第 0 行到第 1 行的路径和为 0
        for (int i = 0; i < m + 2; ++i) {
            dp[0][i] = 0;
        }

        // 用于存储最终的最小下降路径和
        int cur = INT_MAX;

        // 从第 1 行开始，逐行填充 dp 数组
        for (int i = 1; i < n + 1; ++i) {
            for (int j = 1; j < m + 1; ++j) {
                // 对于每个点 (i, j)，计算从上一行的相邻三个点（左上、正上、右上）的最小路径和
                dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
                // 如果已经到达最后一行，更新 cur 为当前的最小值
                if (i == n) {
                    cur = cur > dp[i][j] ? dp[i][j] : cur;
                }
            }
        }

        // 返回最终的最小下降路径和
        return cur;
    }
};

---

174.地下城游戏（地狱）★★★★★

2025小米笔试第二题

2024 大疆秋招笔试题

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        // 获取地下城的行数和列数
        int n = dungeon.size();
        int m = dungeon[0].size();

        // 创建一个动态规划数组 dp，大小为 (n+1) x (m+1)，初始化为 INT_MAX
        // dp[i][j] 表示到达房间 (i, j) 时所需的最少初始健康点数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));

        // 初始化 dp 数组的边界条件
        // 因为骑士从 (n-1, m-1) 向右或向下移动时，需要至少 1 点健康值
        dp[n][m - 1] = dp[n - 1][m] = 1;

        // 从右下角开始，逐行逐列向上和向左填充 dp 数组
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                // 计算到达房间 (i, j) 时所需的最少初始健康点数
                // 从右边或下边的房间到达 (i, j) 时，需要的健康点数减去当前房间的点数
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];

                // 如果计算结果小于 1，则将其设置为 1
                // 因为骑士的健康点数不能小于 1
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        // 返回骑士进入地下城左上角房间所需的最少初始健康点数
        return dp[0][0];
    }
};

---

213.打家劫舍（较简）★★☆☆☆

class Solution {
public:
    // 动态规划函数，用于计算在给定范围内不偷相邻房子的最大金额
    int maxRob(vector<int>& nums, int left, int right) {
        int n = right - left + 1; // 计算范围内的房子数量
        if (n == 1) return nums[left]; // 如果只有一间房子，直接返回其金额
        if (n == 2) return max(nums[left], nums[left + 1]); // 如果有两间房子，返回金额较大的那间

        // 动态规划数组，dp[i] 表示在 [left, left + i] 范围内不偷相邻房子的最大金额
        vector<int> dp(n);
        dp[0] = nums[left]; // 初始化第一间房子的最大金额
        dp[1] = max(nums[left], nums[left + 1]); // 初始化前两间房子的最大金额

        int j = 2; // 动态规划数组的索引
        for (int i = left + 2; i <= right; ++i) {
            // 状态转移方程：当前房子的最大金额等于前一间房子的最大金额和前两间房子的最大金额加上当前房子金额的较大值
            dp[j] = max(dp[j - 1], dp[j - 2] + nums[i]);
            j++;
        }
        return dp[j - 1]; // 返回范围内的最大金额
    }

    // 主函数，用于计算在循环数组中不偷相邻房子的最大金额
    int rob(vector<int>& nums) {
        int n = nums.size(); // 获取房子的数量
        if (n == 0) return 0; // 如果没有房子，返回 0
        if (n == 1) return nums[0]; // 如果只有一间房子，返回其金额
        if (n == 2) return max(nums[0], nums[1]); // 如果有两间房子，返回金额较大的那间
        if (n == 3) return max(max(nums[0], nums[1]), nums[2]); // 如果有三间房子，返回金额最大的那间

        // 计算两种情况的最大金额：
        // 1. 偷第一间房子，不能偷最后一间房子
        int x = nums[0] + maxRob(nums, 2, n - 2);
        // 2. 不偷第一间房子，可以偷最后一间房子
        int y = maxRob(nums, 1, n - 1);

        // 返回两种情况中的最大金额
        return max(x, y);
    }
};