算法——动态规划

class Solution {
public:
    int tribonacci(int n) {
        if(n == 0)
            return 0;
        if(n == 1 || n == 2)
            return 1;

        vector<int> dp(n + 1);
        dp[0] = 0;
        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];
    }
};

三步问题

思路：

状态表示：dp[i] 表示，达到 i 位置时，一共有多少种方法。
动态转移方程：最后一步可走 1 级、2 级或 3 级，所以第 i 个位置的跳法 = i 前一级台阶的跳法（一步跳到 i 位置）+ i 前两级台阶的跳法（一次跳两步，直接跳到 i 位置） + i 前三级台阶的跳法（一次跳三步，直接跳到 i 位置），即 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
初始化：dp[1] = 1，dp[2] = 2，dp[3] = 4。
填表顺序：因为每一个位置都需要前三个位置的值，所以从前向后填表。

代码：

class Solution {
public:
    int waysToStep(int n) {
        if(n == 1 || n == 2)
            return n;
        if(n == 3)
            return 4;
        
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i = 4; i <= n; i++)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2])%1000000007 + dp[i - 3])%1000000007;
        }

        return dp[n];
    }
};

使用最小花费爬楼梯

思路：

状态表示：dp[i] 表示，到达第 i 个位置时，所需要的最小花费。
动态转移方程：要到达第 i 个位置，只能从第 i-1 个位置走 1 步上来（花费为 dp[i-1] + cost[i-1]），或从第 i-2 个位置走 2 步上来（花费为 dp[i-2] + cost[i-2]）；为了得到最小花费，取这两种方式的最小值，即 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。
初始化：dp[0] = 0、dp[1] = 0，表示到达第 0 个和第 1 个位置时无需花费（题目允许从下标 0 或 1 的位置开始爬楼梯）。
填表顺序：因为计算 dp[i] 依赖前两个位置 dp[i-1] 和 dp[i-2] 的值，所以从 i=2 开始，从前向后依次填充 dp 数组直到 i=n（n 为 cost 数组长度，对应楼梯顶部位置）。

代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        //楼梯顶部在数组最后一个元素的后一个位置
        vector<int> dp(n + 1);
        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];
    }
};

解码方法

思路：

状态表示：dp[i] 表示，以 i 为结尾的位置的解码方法总数。
动态转移方程：计算第 i 个位置的解码方法数，分两种合法情况累加
- 若 s[i] != '0'，则当前字符可独立解码，方法数等于前 i - 1个字符的解码数，即 dp[i] += dp[i-1],因为相当于在前 i - 1个字符的每种解码方式上都加上当前数字解码后的字符
- 若第 i 个字符和第 i - 1个字符组成的数字在 [10,26] 之间，则可组合解码，方法数等于前 i - 2 个字符的解码数，即 dp[i] += dp[i-2]，因为相当于在前 i - 2个字符的每种解码方式上都加上第 i 和第 i - 1个数字解码后的字符
初始化：
- 第一个字符 s[0]：若为 '0' 无法解码，直接返回 0；否则 dp[0] = 1
- 若 s[1] != '0'，可单独解码，dp[1] += 1；若 s[0] 和 s[1] 组合数在 [10,26]，可组合解码，dp[1] += 1
填表顺序：因为计算 dp[i] 依赖前两个位置 dp[i-1] 和 dp[i-2] 的值，所以从 i=2 开始，从前向后依次填充 dp 数组直到 i = n - 1。

代码：

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

        for(int i = 2; i < n ; i++)
        {
            if(s[i] != '0')
                dp[i] += dp[i - 1];
            int num = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if(num >= 10 && num <= 26)
                dp[i] += dp[i - 2];
        }

        return dp[n - 1];
    }
};

路径问题

不同路径

思路：

状态表示：dp[i][j]表示从左上角（1,1）位置到 i，j位置有多少不同的路径
动态转移方程：要想到达 i，j位置，只能从上方（i - 1，j）向下走一步，或者从左侧（i，j - 1）向右走一步，所以 i，j位置的总路径数为两种方式的路径之和，即dp[ i ][ j ] = dp[i - 1][ j ] + dp[ i ][j - 1]
初始化：为了避免越界的情况，dp数组比实际需要的大小多开一行和一列，并且多开的这一行和一列都初始化为0，这样对后面计算结果不产生影响，dp[1][1] 初始化为1，表示到达起点位置有一种方式，因为初始位置就在起点，这个位置填充dp表的时候注意不要重复填充，否则会有问题。
填表顺序：因为计算dp[ i ][ j ]的时候依赖上方（dp[i - 1][ j ]）和左侧（dp[ i ][j - 1]），所以直接从上到下遍历每一行，每行内从左到右遍历每一列即可。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[1][1] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == 1 && j == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

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

不同路径 II

思路：

状态表示：dp[i][j]表示从左上角（1,1）位置到 i，j位置有多少不同的路径。
动态转移方程：
- 如果 i，j位置不是障碍物，可以从上方（i - 1，j）向下走一步，或者从左侧（i，j - 1）向右走一步，所以 i，j位置的总路径数为两种方式的路径之和，即dp[ i ][ j ] = dp[i - 1][ j ] + dp[ i ][j - 1]。
- 如果 i，j位置是障碍物，那么这个位置没有方式能到达，所以dp[ i ][ j ] = 0。
初始化：
- 首先注意特殊情况，如果obstacleGrid[0][0] = 1，说明起点就是个障碍物，此时哪里都去不了，直接返回 0。
- 如果起点不是障碍物，则正常初始化：为了避免越界的情况，dp数组比实际需要的大小多开一行和一列，并且多开的这一行和一列都初始化为0，这样对后面计算结果不产生影响，dp[1][1] 初始化为1，表示到达起点位置有一种方式，因为初始位置就在起点，这个位置填充dp表的时候注意不要重复填充，否则会有问题。
填表顺序：
- 因为计算dp[ i ][ j ]的时候依赖上方（dp[i - 1][ j ]）和左侧（dp[ i ][j - 1]），所以直接从上到下遍历每一行，每行内从左到右遍历每一列即可。
- 注意 dp 数组和 obstacleGrid 数组的下标映射关系，因为每个位置的填充还需要通过obstacleGrid判断一下是不是障碍物。

代码：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0] == 1)
            return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[1][1] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == 1 && j == 1)
                    continue;
                if(obstacleGrid[i - 1][j - 1] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

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

珠宝的最高价值

思路：

1.题目大意

给定一个 m × n 的二维数组 frame，数组中每个元素代表对应位置珠宝的价值。你只能从左上角出发，每次向右或向下移动一步，最终到达右下角，求移动路径上能收集到的珠宝最大总价值。

2.状态表示

定义 dp[i][j]：表示从左上角走到第 i 行第 j 列位置时，能收集到的珠宝最大总价值。
数组大小：dp[m+1][n+1]（多开一行一列，避免处理边界越界问题，初始值全为 0）。

3.动态转移方程

到达 (i,j) 位置只有两种路径：

从上方 (i-1,j) 向下走一步到达；
从左侧 (i,j-1) 向右走一步到达。

因此递推公式为：dp[i][j] = max(上方最大值dp[i-1][j], 左侧最大值dp[i][j-1]) + 当前位置珠宝价值frame[i-1][j-1]

注：dp 数组下标比原数组大 1，所以取原数组值用 frame[i-1][j-1]。

4.初始化

第一行 dp[0][j] = 0：没有行，无法走到任何位置，价值为 0；
第一列 dp[i][0] = 0：没有列，无法走到任何位置，价值为 0；
其余位置初始化为 0，直接通过递推公式计算赋值。

5.填表顺序

外层循环遍历行：i 从 1 到 m（从上到下）；
内层循环遍历列：j 从 1 到 n（从左到右）；
顺序：保证计算 dp[i][j] 时，上方 dp[i-1][j] 和左侧 dp[i][j-1] 已经计算完成。

6.最终结果

dp[m][n] 即为从左上角走到右下角的珠宝最大总价值。

代码：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }

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

下降路径最小和

思路：

1. 题目大意
给定一个 n × n 的二维正方形数组 matrix，从第一行任意位置出发，每次可以向正下方、左下方、右下方移动一步，最终到达最后一行，求移动路径上数字的最小和。
2. 状态表示

定义 dp[i][j]：表示从第一行走到第 i 行第 j 列位置时，路径数字的最小总和。
数组大小：dp[n+1][n+2]（多开一行两列，避免处理边界越界问题）。
初始值：除第一行外，其余位置初始化为 INT_MAX（无穷大，保证取最小值时不干扰计算）。

3. 动态转移方程
到达 (i,j) 位置只有三种路径：

从左上方 (i-1,j-1) 向右下走一步到达；
从正上方 (i-1,j) 向正下走一步到达；
从右上方 (i-1,j+1) 向左下走一步到达。

因此递推公式为：

dp[i][j] = min( min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1] ) + 当前位置数字 matrix[i-1][j-1]

注：dp 数组下标比原数组大 1，所以取原数组值用 matrix[i-1][j-1]。

4. dp 数组初始化

第一行 dp[0][i] = 0：虚拟第 0 行所有位置初始和为 0，保证 dp 表第一个有效行（即第 1 行）数据填充的正确性；
其余行初始化为 INT_MAX：保证未计算的位置不会干扰取最小值的逻辑；
多开两列边界：防止访问 j-1/j+1 时数组越界。

5. 填表顺序

外层循环遍历行：i 从 1 到 n（从上到下）；
内层循环遍历列：j 从 1 到 n（从左到右）；
顺序：保证计算 dp[i][j] 时，左上、正上、右上三个位置的最小值已经计算完成。

6. 最终结果
结果在最后一行的所有位置中取最小值：
遍历 dp[n][1] ~ dp[n][n]，找到最小的值即为下降路径最小和。

代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        for(int i = 0; i < n + 2; i++)
            dp[0][i] = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; 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];
            }
        }

        int ret = INT_MAX;
        for(int i = 1; i <= n; i++)
        {
            ret = min(ret, dp[n][i]);
        }

        return ret;
    }
};

最小路径和

思路：

1.题目大意

给定一个 m × n 的二维数组 grid，数组中每个元素表示一个非负整数。你只能从左上角出发，每次向右或向下移动一步，最终到达右下角，求移动路径上所有数字的最小总和。

2.状态表示

定义 dp[i][j]：表示从左上角走到第 i 行第 j 列位置时，路径数字的最小总和。
数组大小：dp[m+1][n+1]（多开一行一列，避免处理边界越界问题）。
初始值：所有位置初始化为 INT_MAX（无穷大，保证取最小值时不干扰计算）。

3.动态转移方程

到达 (i,j) 位置只有两种路径：

从上方 (i-1,j) 向下走一步到达；
从左侧 (i,j-1) 向右走一步到达。

因此递推公式为：dp[i][j] = min(上方最小值dp[i-1][j], 左侧最小值dp[i][j-1]) + 当前位置数字grid[i-1][j-1]

注：dp 数组下标比原数组大 1，所以取原数组值用 grid[i-1][j-1]。

4.dp数组初始化

整体初始化：dp 数组所有元素先赋值为 INT_MAX（无穷大）；
起始点初始化：dp[0][1] = 0、dp[1][0] = 0（为左上角起点 dp[1][1] 提供正确的最小值计算基准）；
多开一行一列：避免边界位置访问越界，简化代码逻辑。

5.填表顺序

外层循环遍历行：i 从 1 到 m（从上到下）；
内层循环遍历列：j 从 1 到 n（从左到右）；
顺序：保证计算 dp[i][j] 时，上方 dp[i-1][j] 和左侧 dp[i][j-1] 已经计算完成。

6.最终结果

dp[m][n] 即为从左上角走到右下角的路径最小总和。

代码：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j -1]) + grid[i - 1][j - 1];
            }
        }

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

地下城游戏

思路：

1. 题目大意
给定一个 m × n 的二维地图 dungeon，每个格子为整数（正数代表加血，负数代表减血）。骑士从左上角出发，每次只能向右或向下移动一步，最终到达右下角救出公主。

要求：骑士在移动过程中任意时刻血量必须 > 0，求骑士出发时需要的最小初始血量。

2. 状态表示

定义 dp[i][j]：表示从第 i 行第 j 列位置出发，到达右下角终点，所需要的最小初始血量（这道题的状态表示要以某一个位置为起点，从后向前求解；如果以某一个位置为结尾，从前向后求，那 dp 表每个位置的值既受到前面值的影响，又受到后面值的影响，没法计算）。
数组大小：dp[m+1][n+1]（多开一行一列，避免处理边界越界问题）。
初始值：所有位置初始化为 INT_MAX（无穷大，保证取最小值时不干扰计算）。

3. 动态转移方程
从 (i,j) 出发只能向右或向下走，到达终点的最小血量由下一步最小血量决定：

下一步可选：下方 dp [i+1][j]、右方 dp [i][j+1]，取两者最小值，因为要最小血量；
当前格子会扣血 / 加血：当前所需血量 = 下一步最小血量 - 当前格子数值（即下一步最小血量 + 当前格子数值的负数，这样当前格子如果是负数，需要扣血，当前位置最小血量就会加上需要的血；如果是正数，能加血，当前位置最小血量就会减去加上的血）；
约束：血量必须 ≥ 1（不能≤0）。

注：如果一个位置的值是正数且非常大，可能导致这里算出来的最小血量是负数，但是这是不合理的，因为负数勇士已经死了，加不上血，所以出现这种情况要将值修改为1，保证勇士是活着的。

因此递推公式为：dp[ i ][ j ] = max(1, min( dp[ i+1 ][ j ], dp[ i ][ j+1 ] ) - dungeon[ i ][ j ] )

注：本题从后往前推导，dp 数组下标与原数组完全对应，直接用 dungeon[i][j]。

4. dp 数组初始化

整体初始化：dp 数组所有元素先赋值为 INT_MAX（无穷大）；
终点后虚拟位置初始化：dp[m][n-1] = 1、dp[m-1][n] = 1（为终点 dp[m-1][n-1] 提供正确的最小值计算基准，终点到达后只需血量≥1 即可）；
多开一行一列：防止边界位置访问越界，简化代码逻辑。

5. 填表顺序

外层循环遍历行：i 从 m-1 到 0（从下往上）；
内层循环遍历列：j 从 n-1 到 0（从右往左）；
顺序：保证计算 dp[i][j] 时，下方 dp[i+1][j] 和右方 dp[i][j+1] 已经计算完成。

6. 最终结果
dp[0][0] 即为从左上角起点出发，所需要的最小初始血量。

代码：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }

        return dp[0][0];
    }
};

简单多状态dp问题

面试题 17.16. 按摩师

思路：

1.题目大意

一个按摩师会接到源源不断的预约请求，每个预约都可以选择接或不接。要求：不能接受相邻的预约，给定一个非负整数数组 nums，数组中的每个元素代表预约的时长，求按摩师能达到的最大总预约时长。

2.状态表示

定义 dp[i]：表示前 i+1 个预约（下标 0 到 i）中，按摩师能获得的最大总收益。
数组大小：dp[n]，与预约数组 nums 长度一致。

3.状态转移方程

对于第 i 个预约，有两种选择：

接：第 i-1 个预约一定不能接，最大收益 = dp[i-2] + nums[i]
不接：最大收益 = dp[i-1]（前 i-1 个预约的最优解）

因此递推公式为：dp[i] = max(接这个预约的收益, 不接这个预约的收益)，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

4. dp 数组初始化

dp[0] = nums[0]：只有 1 个预约，只能接它，收益为本身；
dp[1] = max(nums[0], nums[1])：有 2 个预约，选收益更大的那个；
代码中处理了边界情况：n=0 返回 0，n=1 返回 nums[0]，n=2 返回两者最大值。

5.填表顺序

遍历方向：从前往后遍历预约数组；
循环起始：i 从 2 开始，到 n-1 结束；
顺序：保证计算 dp[i] 时，dp[i-1] 和 dp[i-2] 已经计算完成。

6.最终结果

dp[n-1] 即为所有预约都考虑完时，按摩师能获得的最大总收益。

代码：

class Solution {
public:
    int massage(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        if(n == 2)
            return max(nums[0], nums[1]);
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; i++)
        {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }
};

213. 打家劫舍 II

思路：

1. 题目大意
给定一个环形排列的非负整数数组 nums，数组元素代表每个房屋的金额。
规则：不能同时偷窃相邻的房屋，且第一个和最后一个房屋相邻（首尾相连），求能偷窃到的最大总金额。
2. 状态表示

定义 dp[i]：表示在指定区间 [left, i] 的房屋中，能偷窃到的最大总金额。
数组大小：dp[right + 1]，适配传入的区间右边界。
核心拆解：环形数组 → 拆分成两种情况分类处理。
- 偷第一个位置：因为是环形的，偷了第一个位置，第二个位置和最后一个位置都不能偷，所以结果就是对第三个位置到倒数第二个位置进行一次打家劫舍一，然后加上nums[0]。
- 不偷第一个位置：因为环形，第一个位置没有被偷，那么第二个位置和最后一个位置都可以偷，就相当于从第二个位置到最后一个位置进行一次打家劫舍一。

3. 状态转移方程
对于第 i 个房屋，有两种选择：

偷：第 i-1 个一定不能偷，最大金额 = dp[i-2] + nums[i]
不偷：最大金额 = dp[i-1]（前 i-1 个的最优解）

因此递推公式为：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
4. dp 数组初始化

在区间 [left, right] 内：
- dp[left] = nums[left]：只有一间房，偷它；
- dp[left + 1] = max(nums[left], nums[left + 1])：两间房，偷金额大的；
边界判断：left > right 返回 0（无房可偷），left == right 返回当前房屋金额（只有一间房）。

5. 填表顺序

遍历方向：从前往后遍历指定区间；
循环起始：i 从 left + 2 开始，到 right 结束；
顺序：保证计算 dp[i] 时，dp[i-1] 和 dp[i-2] 已经计算完成。

6. 最终结果

环形问题拆分为两种情况，取最大值：
- 偷第一个，不偷最后一个：计算区间 [2, n-2] + 第一个房屋 nums[0]
- 不偷第一个，偷最后一个：计算区间 [1, n-1]
最终结果：max(情况1, 情况2)

代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        return max(nums[0] + _rob(nums, 2, n - 2), _rob(nums, 1, n - 1));
    }

    int _rob(vector<int>& nums, int left, int right)
    {
        if(left > right)
            return 0;
        if(left == right)
            return nums[left];

        vector<int> dp(right + 1, 0);
        dp[left] = nums[left];
        dp[left + 1] = max(nums[left], nums[left + 1]);
        for(int i = left + 2; i <= right; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[right];
    }
};

740. 删除并获得点数

思路：

1.题目大意

给定一个整数数组 nums，你可以选择删除一个数字 x，并获得 x 点数，但是删除后必须同时删除所有等于 x-1 和 x+1 的数字。求按照规则操作，能获得的最大总点数。

2.状态表示

辅助数组 arr：
- 大小：max(nums)+1
- 含义：arr[x] 表示所有值为 x 的数字的总点数（即值 x 作为下标，对应数组位置填充所有出现的 x 相加后的总和）
dp 数组：
- 定义：dp[i] 表示在 0~i 数字范围内，能获得的最大总点数。
- 大小：与辅助数组 arr 长度一致。

3.状态转移方程

本题等价于打家劫舍问题：选了数字 x，就不能选 x-1 和 x+1。在 arr 数组中的表现就是选了下标为 i 位置的值，就不能选下标为 i - 1 和 i + 1 位置的值。对于第 i 个数字，有两种选择：

选：不能选 i-1，总点数 = dp[i-2] + arr[i]
不选：总点数 = dp[i-1]

因此递推公式为：dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])

4.预处理 + dp 数组初始化

预处理（核心转化）：
- 遍历原数组 nums，统计每个数字的总点数，存入 arr 数组，将问题转化为打家劫舍。
初始化：
- dp[0] = arr[0]：只有数字 0，选它获得对应点数；
- dp[1] = max(arr[0], arr[1])：数字 0 和 1，选点数更大的那个。

5.填表顺序

遍历方向：从前往后遍历辅助数组 arr；
循环起始：i 从 2 开始，到数组末尾结束；
顺序：保证计算 dp[i] 时，dp[i-1] 和 dp[i-2] 已经计算完成。

6.最终结果

调用转化后的打家劫舍函数，返回 dp[n-1]，即为能获得的最大总点数。

代码：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int mx = ranges::max(nums);
        vector<int> arr(mx + 1, 0);
        for(auto e : nums)
        {
            arr[e] += e;
        }

        return rob(arr);
    }

    int rob(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        if(n > 1)
            dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
};

LCR 091. 粉刷房子

思路：

1. 题目大意
有 n 个房子排成一排，每个房子可以刷成红、蓝、绿三种颜色中的一种，不同颜色粉刷价格不同。
要求：相邻的两个房子颜色不能相同，给定 n×3 的价格数组 costs（costs[i][j] 表示第 i 个房子刷第 j 种颜色的花费），求刷完所有房子的最小总花费。
2. 状态表示

定义 dp[i][j]：表示粉刷完第 i 个房子，且第 i 个房子刷成第 j 种颜色时的最小总花费（j=0,1,2 对应三种颜色）。
数组大小：dp[m][3]，m 为房子数量，固定 3 列对应三种颜色。

3. 状态转移方程
核心规则：当前房子颜色 ≠ 上一个房子颜色，因此当前颜色的最小花费 = 上一个房子另外两种颜色的最小花费 + 当前颜色花费。

第 i 个房子刷颜色 0：dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]
第 i 个房子刷颜色 1：dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]
第 i 个房子刷颜色 2：dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]

4. dp 数组初始化
第一个房子（i=0）没有上一个房子，直接赋值为对应颜色的花费：

dp[0][0] = costs[0][0]
dp[0][1] = costs[0][1]
dp[0][2] = costs[0][2]

5. 填表顺序

遍历方向：从前往后遍历房子（从上到下）；
循环起始：i 从 1 开始，到 m-1 结束；
顺序：保证计算 dp[i][j] 时，上一个房子的所有颜色花费 dp[i-1][0/1/2] 已经计算完成。

6. 最终结果
最后一个房子可以刷三种颜色中的任意一种，在最后一行的三个值中取最小值：
min(dp[m-1][0], dp[m-1][1], dp[m-1][2]) 即为粉刷所有房子的最小总花费。

代码：

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int m = costs.size();
        vector<vector<int>> dp(m, vector<int>(3));
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        for(int i = 1; i < m; i++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
        }

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

309. 买卖股票的最佳时机含冷冻期

思路：

1.题目大意

给定一个整数数组 prices，prices[i] 表示第 i 天的股票价格，卖出股票后，无法在第二天买入股票（冷冻期），每天只能进行买入 / 卖出 / 不操作中的一种，且任何时候最多只能持有一股股票，求能获得的最大利润。

2.状态表示

定义 dp[i][j]：i 表示第 i 天，j 表示当天的状态，dp[i][j] 表示第 i 天处于状态 j 时的最大利润。
状态划分（固定 3 种状态）：
- j=0：买入状态（当天结束后持有股票）
- j=1：卖出状态（当天卖出股票）
- j=2：冷冻期状态（当天不持有股票，且不是当天卖出）
数组大小：dp[n][3]，n 为天数，固定 3 列对应 3 种状态，初始值全为 0。

3.状态转移方程

每个状态只能由合法的前序状态转移而来，核心状态转移逻辑：

第 i 天为买入状态（dp [i][0]）两种情况：① 前一天已经买入，当天不操作；② 前一天是冷冻期，当天买入dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
第 i 天为卖出状态（dp [i][1]）只能：前一天持有股票，当天卖出（唯一转移方式）dp[i][1] = dp[i-1][0] + prices[i]
第 i 天为冷冻期状态（dp [i][2]）两种情况：① 前一天是冷冻期，当天不操作；② 前一天卖出股票，当天进入冷冻期dp[i][2] = max(dp[i-1][2], dp[i-1][1])

4.dp数组初始化

第 0 天（第一天）：
- 买入状态：dp[0][0] = -prices[0]（买入股票，利润为负的股价）
- 卖出状态：dp[0][1] = 0（无法卖出，利润为 0）
- 冷冻期状态：dp[0][2] = 0（无冷冻期，利润为 0）

5.填表顺序

遍历方向：从前往后遍历天数（从第 1 天到最后 1 天）；
循环起始：i 从 1 开始，到 n-1 结束；
顺序：保证计算第 i 天状态时，第 i-1 天的所有状态已计算完成。

6. 最终结果

最大利润只能出现在无股票的状态（卖出 / 冷冻期），因此取最后一天两个状态的最大值：max(dp[n-1][1], dp[n-1][2]) 即为最大利润

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3, 0));  // 0-买入，1-卖出，2-冷冻期
        dp[0][0] = -prices[0];
        for(int i = 1; i < n; i++)
        {
            //可以从买入到买入状态，只需要前面买入，当天什么都不做就可
            //也可以从冷冻期到买入，前一天是冷冻期，当天可以买入
            dp[i][0] =  max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            //只能从买入到卖出，前面买入，当天卖出
            dp[i][1] = dp[i - 1][0] + prices[i];
            //如果前一天冷冻期，当天什么也不做，相当于当天也是冷冻期，所以可以从冷冻期到冷冻期
            //也可以从买入到冷冻期
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1]);
        }

        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

714. 买卖股票的最佳时机含手续费

思路：

1. 题目大意
给定一个整数数组 prices，prices[i] 表示第 i 天的股票价格，每次卖出股票都需要支付一笔固定手续费，每天可以进行任意次买卖操作，但任何时候最多只能持有一股股票，求能获得的最大利润。
2. 状态表示

定义 dp[i][j]：i 表示第 i 天，j 表示当天的持有状态，dp[i][j] 表示第 i 天处于状态 j 时的最大利润。
状态划分（固定 2 种状态）：
- j=0：买入 / 持有状态（当天结束后持有股票）
- j=1：卖出 / 不持有状态（当天结束后不持有股票）
数组大小：dp[n][2]，n 为总天数，固定 2 列对应两种状态。

3. 状态转移方程
每个状态由前一天的合法状态转移而来，核心是卖出时扣除手续费：
第 i 天持有股票（dp [i][0]）

两种情况：
- 前一天已经持有，当天不操作；
- 前一天不持有，当天买入股票。
公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

第 i 天不持有股票（dp [i][1]）

两种情况：
- 前一天就不持有，当天不操作；
- 前一天持有，当天卖出股票（卖出时减去手续费）。
公式：dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)

4. dp 数组初始化

第 0 天（第一天）：
- 持有股票：dp[0][0] = -prices[0]（买入股票，利润为负的股价）；
- 不持有股票：dp[0][1] = 0（不操作，利润为 0）。

5. 填表顺序

遍历方向：从前往后遍历天数；
循环起始：i 从 1 开始，到 n-1 结束；
顺序：保证计算第 i 天状态时，第 i-1 天的所有状态已经计算完成。

6. 最终结果
最大利润一定出现在最后一天不持有股票的状态（持有股票无法获得最大利润），直接返回：
dp[n-1][1]

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0)); //dp[i][0]-买入，dp[i][1]-卖出
        dp[0][0] = -prices[0];
        for(int i = 1; i < n; i++)
        {
            //可以从买入到买入，只需要前面买入，当天什么都不做
            //可以从卖出到买入
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            //手续费一轮交易只花一次，这里卖出的时候减去手续费
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }

        //最后买入的位置一定不是结果，因为手里还有没卖的股票呢
        return dp[n - 1][1];
    }
};

123. 买卖股票的最佳时机 III

思路：

1. 题目大意
给定一个整数数组 prices，prices[i] 表示第 i 天的股票价格，最多只能完成 2 笔交易（不能同时持有多股股票，卖出后才能再次买入），求能获得的最大利润。
2. 状态表示

使用两个二维 dp 数组区分状态，核心维度：天数 + 已完成交易次数
- f[i][j]：表示第 i 天结束后，恰好完成 j 笔交易，且当前持有股票时的最大利润
- g[i][j]：表示第 i 天结束后，恰好完成 j 笔交易，且当前不持有股票时的最大利润
交易次数 j 取值：0、1、2（最多 2 笔交易）
初始化：数组初始值为 -0x3f3f3f3f（很小的值，表示非法状态，保证取最大值时不干扰，并且取到这个值时减去某天的价格不会溢出，INT_MIN会有溢出的问题）

3. 状态转移方程
持有股票状态 f [i][j]

只能由两种合法状态转移而来：
- 前一天已经持有股票，当天不操作
- 前一天不持有股票，当天买入股票
公式：f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i])

不持有股票状态 g [i][j]

两种情况：
- 前一天不持有股票，当天不操作
- 前一天持有股票，当天卖出（卖出完成 1 笔交易，交易次数 + 1）
公式：g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])（j≥1 时才能卖出转移）

4. dp 数组初始化

第 0 天（第一天）：
- 持有股票：f[0][0] = -prices[0]（第 0 天买入股票，0 笔交易完成）
- 不持有股票：g[0][0] = 0（第 0 天不操作，0 笔交易完成）
其余状态：-0x3f3f3f3f（很小的值，表示非法状态，保证取最大值时不干扰，并且取到这个值时减去某天的价格不会溢出，INT_MIN会有溢出的问题）

5. 填表顺序

外层循环：从前往后遍历天数，i 从 1 到 n-1
内层循环：遍历交易次数，j 从 0 到 2
顺序：保证计算第 i 天状态时，第 i-1 天的所有状态已计算完成

6. 最终结果
最大利润一定出现在最后一天不持有股票的状态，且交易次数为 0/1/2 次
遍历 g[n-1][0]、g[n-1][1]、g[n-1][2] 取最大值，即为所求最大利润

代码：

class Solution 
{
    const int INF = 0x3f3f3f3f;
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j]  - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0)
                {
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for(int j = 0; j < 3; j++)
        {
            ret = max(ret, g[n - 1][j]);
        }

        return ret;
    }
};

188. 买卖股票的最佳时机 IV

思路：

1.题目大意

给定一个整数数组 prices，prices[i] 表示第 i 天的股票价格，最多只能完成 k 笔交易（不能同时持有多股股票，卖出后才算完成一笔交易），求能获得的最大利润。

2.状态表示

f[i][j]：第 i 天结束后，恰好完成 j 笔交易，且当前持有股票的最大利润。
g[i][j]：第 i 天结束后，恰好完成 j 笔交易，且当前不持有股票的最大利润。
状态维度：n × (k+1)，n 为天数，j 范围 0 ~ k。
初始值：全部设为无穷小（INF），表示未定义 / 非法状态。

3.动态转移方程

与股票 III 完全一致，只是交易次数从固定 2 次变成变量 k 次：

持有股票 f [i][j]
- 前一天已持有：f[i-1][j]
- 前一天不持有，当天买入：g[i-1][j] - prices[i]
- 公式：f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i])
不持有股票 g [i][j]
- 前一天不持有：g[i-1][j]
- 前一天持有，当天卖出（交易次数 +1）：f[i-1][j-1] + prices[i]
- 公式：g[i][j] = max(g[i-1][j], j>=1 ? f[i-1][j-1] + prices[i] : INF)

4.dp数组初始化

第 0 天：
- 持有股票：f[0][0] = -prices[0]
- 不持有股票：g[0][0] = 0
- 其余状态：INF（非法）

5.填表顺序

外层：i 从 1 到 n-1（遍历天数）
内层：j 从 0 到 k（遍历交易次数）

6. 最终结果

在最后一天不持有股票的所有状态中取最大值：max(g[n-1][0], g[n-1][1], ..., g[n-1][k])

注意：

一次交易至少需要 2 天（买 + 卖），n 天最多只能完成 n/2 笔有效交易
如果 k > n/2，等价于无限次交易，直接缩到 n/2 避免空间 / 时间浪费

代码：

class Solution {
    int INF = -0X3f3f3f3f;
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        k = min(k, n / 2);
        vector<vector<int>> f(n, vector<int>(k + 1, INF));
        vector<vector<int>> g(n, vector<int>(k + 1, INF));
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0)
                {
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for(int i = 0; i <= k; i++)
        {
            ret = max(ret, g[n - 1][i]);
        }

        return ret;
    }
};