算法加训之动态规划 dp 上---上（一维动态规划）

用户11956880

发布于 2025-12-18 18:17:50

860

dp as is known to all 很难哈，今天就在这里作为我对dp的开始（虽然前俩月学过点，但是已经石沉大海了），我们嗯....就从这里变强哈

70. 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

https://leetcode.cn/problems/climbing-stairs/description/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

思路

子问题，当求爬到第i层的方法数量，那就是爬到第i-1和i-2层的方法之和，因为这两次都能一步到达

状态转移方程

最后一步的选择：

如果最后一步爬 1阶，则之前需要爬到 i-1 阶（方法数为 dp[i-1]）。

如果最后一步爬 2阶，则之前需要爬到 i-2 阶（方法数为 dp[i-2]）。

方程： dp[i] = dp[i-1] + dp[i-2]

class Solution {
public:
    int climbStairs(int n) {
        vector<long long int>dp(n+1,0);//就按题目要求的来定义，爬到第i层的方法数量
        //爬到第n层的数量是不是就是爬到第i-1和i-2层的方法数量之和，因为这两次都是需要一步就可以上第n层
        if(n<=2) return n;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];

        }
        return (int )dp[n];
    }
};

983. 最低票价

https://leetcode.cn/problems/minimum-cost-for-tickets/

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

提示：

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

思路

as is know to all 动态规划的状态定义和状态转移(转移方程)是最重要的，我们要先想这俩，这题的状态定义是前i个旅行天所消耗的最少费用，转移方程是dp[j] = min(dp[j], dp[i] + costs[k]);这一会看代码就知道啥意思了。然后我们再说细节，这个题换个说法就是，用不同价格和长度的贴纸贴住一个长度为n的长方形（把days数组看成一个长方形，贴的是这个数组里的天数，而不是索引长度），然后问选哪些贴纸以及贴的方式，贴完后最便宜，咱们从前贴到后，我们有三个贴纸可以选，每选一个当然会影响后面（这就是重点，我们的选择会互相影响，这就是dp的特点），我们最多有n次选择，也就是这个days数组的长度，每次选择里我们可以有三个选择，选哪些长度，然后用dp记录挑选择后每个长度，其实我所说的这些思路还是你先看代码看会后，配合着在消化比较好

动态规划本质：不是显式地做 n 次选择，而是通过状态转移覆盖所有可能性。

class Solution {
public:
    int duration[3]={1,7,30};//
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n=days.size();
        vector<int>dp(n+1,INT_MAX);
        dp[0]=0;//定义为前i个旅行天消耗掉的钱
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                int end_day=days[i]+duration[j]-1;//用索引为j的票后可覆盖到的天数
                int k=upper_bound(days.begin(),days.end(),end_day)-days.begin();
                //找到第一个大于end_day
                if(dp[i]!=INT_MAX){
                    dp[k]=min(dp[k],dp[i]+costs[j]);
                }
            }
        }
        return dp[n];
    }
};

91. 解码方法

https://leetcode.cn/problems/decode-ways/

一条包含字母 A-Z 的消息通过以下映射进行了编码：

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。

例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1, 1, 10, 6)
"KJF" ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。

注意，可能存在无法解码的字符串。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位 的整数。

示例 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" 并不等价）。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

思路

dp的特点是啥是我们对每个地方做出的选择会影响其他地方，（我们先说正着递推)，先说一下这题的dp含义，就是前i个数所解码的不同方式的个数，然后看状态转移，我们不急着想咋转移，我们先看怎么个状态，比如11，他可以是单独看一个字符然后变成AA，也可以一下看两个，变成K，那当我们看前i个数解码，

需要记得到是，前i个数对应的是第i-1个数，字符串是从索引0开始的哈

我们只是把转移方程写出来，但是转移还需要在一定条件下，当第i-1是0那我们就不加，当两个数一起解码时，他的数量不在10到26里面也不加

我顺便把倒着递推代码也写上了哈，思想是一样的，其实感觉正着更舒服些哈

//正着递推
class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        if (n==0) return 0; // 空字符串直接返回0
        vector<int>dp(n+1,0);
        dp[0]=1;// 空字符串有一种解码方式
        dp[1]=(s[0]=='0')?0:1; // 初始化第一个字符的解码方式
        for(int i=2;i<=n;i++) {
            // 单独解码当前字符（s[i-1]不为'0'）
            if(s[i-1]!='0') {
                dp[i]+=dp[i-1];
            }
            // 组合解码前两个字符（需满足10到26范围内）
            int two_digit=(s[i-2]-'0')*10+(s[i-1]-'0');
            if (two_digit>=10&&two_digit<=26){
                dp[i]+=dp[i-2];
            }
        }
        return dp[n];
    }
};
//逆着递推
class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n+1);
        dp[n]=1;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='0')
            dp[i]=0;
            else{
                dp[i]=dp[i+1];
                if(i+1<s.size()&&(s[i]-'0')*10+s[i+1]-'0'<=26){
                    dp[i]+=dp[i+2];
                }
            }
        }
        return dp[0];
    }
};

639. 解码方法 II

https://leetcode.cn/problems/decode-ways-ii/

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：

"AAJF" 对应分组 (1 1 10 6)
"KJF" 对应分组 (11 10 6)

注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回解码该字符串的方法数目。

由于答案数目可能非常大，返回 109 + 7 的模。

示例 1：

输入：s = "*"
输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
因此，"*" 总共有 9 种解码方法。

示例 2：

输入：s = "1*"
输出：18
解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。
每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。
因此，"1*" 共有 9 * 2 = 18 种解码方法。

示例 3：

输入：s = "2*"
输出：15
解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。
"21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。
因此，"2*" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。

提示：

1 <= s.length <= 105
s[i] 是 0 - 9 中的一位数字或字符 '*'

思路

和上面思想是一样的哈，只是又多了不同的状态而已，我们直接看代码就行，肯定能看懂

class Solution {
public:
    const int MOD = 1e9 + 7;
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0) return 0;

        vector<long> dp(n + 1, 0);
        dp[0] = 1; // 空字符串的基准情况

        // 处理第一个字符（i=1）
        if (s[0] == '0') {
            dp[1] = 0;
        } else if (s[0] == '*') {
            dp[1] = 9;
        } else {
            dp[1] = 1;
        }

        for (int i = 2; i <= n; ++i) {
            char curr = s[i - 1];   // 当前字符
            char prev = s[i - 2];   // 前一个字符

            // 单独解码当前字符
            if (curr == '*') {
                dp[i] = (dp[i] + 9 * dp[i - 1]) % MOD;
            } else if (curr != '0') {
                dp[i] = (dp[i] + dp[i - 1]) % MOD;
            }

            // 组合解码前两个字符
            if (prev == '*') {
                if (curr == '*') {
                    // ** 的组合：11~19（9种） + 21~26（6种） → 15种
                    dp[i] = (dp[i] + 15 * dp[i - 2]) % MOD;
                } else if (curr <= '6') {
                    // *X（X≤6）: 前一个*可以是1或2 → 2种
                    dp[i] = (dp[i] + 2 * dp[i - 2]) % MOD;
                } else {
                    // *X（X>6）: 前一个*只能是1 → 1种
                    dp[i] = (dp[i] + dp[i - 2]) % MOD;
                }
            } else if (prev == '1') {
                if (curr == '*') {
                    // 1* → 9种（1~9）
                    dp[i] = (dp[i] + 9 * dp[i - 2]) % MOD;
                } else {
                    // 1X → 1种
                    dp[i] = (dp[i] + dp[i - 2]) % MOD;
                }
            } else if (prev == '2') {
                if (curr == '*') {
                    // 2* → 6种（1~6）
                    dp[i] = (dp[i] + 6 * dp[i - 2]) % MOD;
                } else if (curr <= '6') {
                    // 2X（X≤6） → 1种
                    dp[i] = (dp[i] + dp[i - 2]) % MOD;
                }
            } else if (prev != '0') {
                // 普通数字组合（如3X，但3X>26无法解码）
                // 不需要处理
            }

            // 处理前一个字符是0的情况（无法组合解码）
        }

        return (int)dp[n];
    }
};

32. 最长有效括号

https://leetcode.cn/problems/longest-valid-parentheses/

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

思路

dp真的难啊啊啊啊啊啊啊，这题要我们求出一个字符串里最长的有效字符串，那我们定义dp含义为i位置左边到i为止最长有效括号的长度，什么叫tm的状态转移，就是当我们要算第i位置时的dp值，是由i为止前的dp值做上一些操作然后把他的值传给i位置的dp值，先提前说一下我们既然这样定义那遇到（这个位置的dp值必然为0，因为他与左边某个括号不可能匹配，那我们就找），举个例子吧（（）），这几个对应的分别是0 0 2 4，当遇到第三个扩阿訇时候我们看第二个括号对应的dp值是0，那我们就要看i-0-1位置是不是（，是的话dp[2]=dp[1]+2,然后我们再看第四个括号，然后我们就要看i-2-1位置是不是（，是的话第三个的dp值是2所以dp[3]=dp[2]+2,。再举个例子（（））（），按照上面那个所说dp[4]=0最后一个括号是),然后找到对应的是dp[4]，但是你会发现dp[5]不能等于2，他应该等于6，因为看到4位置的（他是0，但是如果右边出现），会导致出现一个匹配的括号，然后就会把整个状态改变，我们需要加上后面那四个，看代码吧，我真不知道咋解释了啊啊啊啊啊啊啊啊，你们看看代码，我也看看代码，应该就懂了，这些东西需要不断地常识，不断地举例子去观察此案呢个得出状态转移方程，好邪乎啊啊啊啊啊啊啊

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.size();
        //定义一下dp值，dp[i]就是从左边某位置到i最长有效括号长度
        vector<int> dp(n+1,0);
        for(int i=1;i<n;i++){
          if(s[i]==')'){
            int p=i-dp[i-1]-1;//找到他前面的那一块的有效括号长度坐标那个不是有小括号的地方
            if(p>=0&&s[p]=='('){
                dp[i]+=dp[i-1]+2+(p>0?dp[p-1]:0);
            }
          }
        }
        return *max_element(dp.begin(),dp.end());
    }
};

198. 打家劫舍

https://leetcode.cn/problems/house-robber/

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

思路

题目说了不能抢相邻家里的，那就是说抢了第i个就不能抢第i-1，i+1了，那我们得到的值就是dp[i-2]+nums[i]是吧，那不抢第i个，我们的值就是抢到第i-1时候的最大值了吧，也就是dp[i-1]应该是吧哈哈，那我们想要打劫出来最大的数的话是不是就是要取个max哈，嗯没座！！！！,但是数组是从0开始的，dp数组我是从1开始定义的，这里别弄错

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

53. 最大子数组和

https://leetcode.cn/problems/maximum-subarray/

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路

用dp写的话，那就是我们dp[i]=max(nums[i],dp[i-1]+nums[i])，dp[i]记录从左边某个地方开始到i位置的最大和，如果第dp[i-1]+当前这个数比这个数单独的小，按我们就以这个数为起始位置开始就行，

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp(n);
        dp[0] = nums[0];
        int maxSum = dp[0];

        for (int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            maxSum = max(maxSum, dp[i]);
        }

        return maxSum;
    }
};

467. 环绕字符串中唯一的子字符串

https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

示例 1：

输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

提示：

1 <= s.length <= 105
s字符串都是小写字母组成

思路

依旧注意看哈，哈哈，我们发现以一个字母结尾的有效字符串（就是按照题意的字符串）的长度就是以该字符串结尾的所有子字符串的数量，比如abc，abc bc c这三个就是所有的以c结尾的字子符串，然后我们顺势发现，如果计算出了以b结尾的子字符串的数量（就是2），然后发现下一个字符是c，那我们就直接顺着2+1，得到了以c结尾的字符串了是吧，那我们就得到了转移方程，if(判断是不是按顺序的字符)，dp[i]=d[i-1]+1;else XXXXX是吧，但是如果这样写了后就是第一个代码，他是错误的，我们要求的dp值是最长长度，就是第二个代码大家看看就懂什么意思了

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n=s.size();
        //1, dp含义的定义
        vector<int>dp(26,0);
        //以第i个字母结尾的字符串的长度最长是多少
        //举个例子zab,长度是3,那么以b结尾的子字符串就有三个是吧哈哈
        
        //2,初始化
        dp[s[0]-'a']=1;
        
        //3，核心代码
        for(int i=1,len=1;i<n;i++){
            int pre=s[i-1]-'a';
            int cur=s[i]-'a';
            if((pre+1)%26==cur){
                dp[cur]=dp[pre]+1;
                len+=1;
            }
            else{
                len=1;
                dp[cur]=1;
            }
        }
        int ans=0;
        for(int i=0;i<26;i++){
            ans+=dp[i];
        }
        return ans;
    }
};

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n=s.size();
        //1, dp含义的定义
        vector<int>dp(26,0);
        //以第i个字母结尾的字符串的长度最长是多少
        //举个例子zab,长度是3,那么以b结尾的子字符串就有三个是吧哈哈
        
        //2,初始化
        dp[s[0]-'a']=1;
        
        //3，核心代码
        for(int i=1,len=1;i<n;i++){
            int pre=s[i-1]-'a';
            int cur=s[i]-'a';
            if((pre+1)%26==cur){
                len+=1;
            }
            else{
                len=1;
            }
            dp[cur]=max(len,dp[cur]);
        }
        int ans=0;
        for(int i=0;i<26;i++){
            ans+=dp[i];
        }
        return ans;
    }
};

940. 不同的子序列 II

https://leetcode.cn/problems/distinct-subsequences-ii/

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

思路

这个状态转移是怎么转移呢，唉，我们初始化一个空字符串，让他的长度为1，然后你看一下我这个图片

画波浪线的就是最后减去的，就是6个序列，大体思路是，我们遍历这个字符串，然后记录当前遍历导的字符所含有的子序列，怎么记录呢，看这个图就能看懂应该，我是真描述不出来了（我是笨蛋），然后呢我们用一个变量len记录当前遍历导的字符的上一个字符时的子序列数量，再用一个变量newadd来记录遍历到当前字符时比之前的子序列多的数量，唉，看代码吧，真tm叙述

状态转移

当遍历到字符 c 时：

新增子序列数量 = 当前总子序列数 - 上次以 c 结尾的子序列数
- 即 newadd = len - dp[c]
- 意义：在之前所有子序列后添加 c，减去已存在的以 c 结尾的子序列（避免重复）
更新以 c 结尾的子序列数：
- dp[c] = dp[c] + newadd
- 意义：合并原有和新增的子序列
更新总子序列数：
- len = len + newadd

初始化

len = 1：表示空序列（后续会减去）
dp 数组全为 0：表示初始时无子序列

class Solution {
public:
    int distinctSubseqII(string s) {
        int n=s.size();
        vector<int>dp(26,0);
        //初始化空字符串的长度是1，很神奇的这个初始化
        //也代表着以每个字符结尾的时的字符串的子序列数量
        int len=1;
        //newadd激素当遇到当前字符结尾时，然后我们1111可能会有重复的子序列出现
        //这个变量就是为了保证这个的
        int newadd=0;
        int mod=1000000007;
        for(char c:s){
            newadd=(len-dp[c-'a'])%mod;
            dp[c-'a']=(dp[c-'a']+newadd)%mod;
            len=(len+newadd)%mod;
        }
        return (len-1+mod)%mod;
    }
};

322. 零钱兑换

https://leetcode.cn/problems/coin-change/

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins =

[1, 2, 5]

, amount =

输出：

解释：11 = 5 + 5 + 1

示例 2：

输入：coins =

[2]

, amount =

输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

思路

创建一个大小为 amount + 1 的整数向量 dp。 dp[i] 将存储组成金额 i 所需的最少硬币数量。所有元素都初始化为 amount + 1。这是一个技巧，用于表示“无穷大”或“无法组成”。之所以使用 amount + 1，是因为所需的最多硬币数量不可能是 amount 本身，因为如果所有硬币面额都为 1，则组成 amount 也只需 amount 个硬币。因此，任何大于 amount 的值都可用作初始的 "无穷大" 值。 dp[0] = 0; 将 dp[0] 设置为 0，因为组成金额 0 需要 0 个硬币。这是动态规划的基础情况。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp(amount+1,amount+1);
        //定义为组成i所要花费硬币最小数量
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(coins[j]<=i){
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
};

300. 最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

思路

状态定义： dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

目标：最终结果为 dp 数组中的最大值，因为最长递增子序列可能以任意位置结尾。

状态转移方程 对于每个元素 nums[i]，需要检查它之前的所有元素 nums[j]（j < i）：

条件：如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 之后形成一个更长的递增子序列。

转移： dp[i] = max(dp[i], dp[j] + 1) 即在所有满足条件的 j 中，找到最大的 dp[j]，然后加 1。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

152. 乘积最大子数组

https://leetcode.cn/problems/maximum-product-subarray/

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出:

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都保证是一个 32-位 整数

思路

max_dp[i]：以 nums[i] 结尾的子数组的最大乘积。

min_dp[i]：以 nums[i] 结尾的子数组的最小乘积。

用两个搭配、数组因为

符号变化：负数相乘会改变符号，可能将最小乘积变为最大。

零值处理：遇到零时，乘积会归零，需重新开始计算。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> max_dp(n);
        vector<int> min_dp(n);
        max_dp[0] = nums[0];
        min_dp[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < n; ++i) {
            max_dp[i] = max({nums[i], max_dp[i - 1] * nums[i], min_dp[i - 1] * nums[i]});
            min_dp[i] = min({nums[i], max_dp[i - 1] * nums[i], min_dp[i - 1] * nums[i]});
            result = max(result, max_dp[i]);
        }
        return result;
    }
};

413. 等差数列划分

https://leetcode.cn/problems/arithmetic-slices/

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1]
输出：0

提示：

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000

思路

我们定义dp数组，dp[i]就是以nums[i]结尾的等差数列数量，我拿例子讲讲吧就是假设1 2 3是dp[3]=1,对吧。然后现在来了个4，我们的判断是4-3==3-2,也就是2 3 4是不是等差，是的话dp[4]=dp[3]加1，因为在原有的1 2 3 加个4 所以1 2 3 4就是个等差，然后再加5 那就是3 4 5是一个，然后2 3 4 5,1 2 3 4 5又是两，就是我想说的是，我们的转移方程就是在原有的基础子数组里加一个数，那他就是还是个子数组，所以我们只需把原有的加回来再加一个新出来的那三个项的子数组就行

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

139. 单词拆分

https://leetcode.cn/problems/word-break/

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

思路

我这个是看题解写的，我一直对字符串很不熟悉，唉，凑合看吧

就是核心就是，我们用两个for循环，外层是当前字符串的位置遍历，下面是要分割位置的遍历，

如果该位置能分割出字典里的单词，并且分割点之前也分割过，就说明能分割，其实看着代码顺着过一遍就能看懂，我是真没法想出来啊啊啊啊啊

2. 动态规划状态定义 dp[i]：表示字符串的前 i 个字符（即 s[0..i-1]）是否可以被分割为字典中的单词。

目标：求 dp[s.length()] 的值（即整个字符串是否可分割）。

3. 状态转移逻辑 对于每个位置 i，检查所有可能的分割点 j（0 ≤ j < i）：

若 dp[j] == true（前 j 个字符可分割）；

且子串 s[j..i-1] 存在于字典中；

则 dp[i] = true。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int n=s.size();
        vector<bool>dp(n+1,false);
        dp[0]=true; // 空字符串可分割

        for(int i=1;i<=n;i++) {          // i表示当前子串长度
            for(int j=0;j<i;j++){       // j为分割点
                if(dp[j]&&dict.count(s.substr(j,i-j))){
                    dp[i]=true;
                    break; // 找到一个有效分割即可退出内层循环
                }
            }
        }
        return dp[n];
    }
};

这几道题并没有发生啥质变，我现在唯一进步的就是感觉很容易看懂人家的简单代码了，唉，啧，难搞啊

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除

动态规划

数组

算法

字符串

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！