codetop标签动态规划大全C++讲解(上)！！动态规划刷穿地心！！学吐了家人们o(╥﹏╥)o

本文主要是介绍codetop标签动态规划大全C++讲解(上)！！动态规划刷穿地心！！学吐了家人们o(╥﹏╥)o，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.零钱兑换

给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

dp[n]的意义为凑成总金额n，最少需要dp[n]枚硬币
amount怎么来的?撤回一个硬币+1来的，dp[i] = min(dp[i]， dp[i - coin] + 1)，其中是coin的原因是，到底撤回面值多少的硬币，还需要穷举
另外，要取min所以dp应该初始化为一个较大值，不能是INT_MAX，因为递推式是dp+1，会溢出

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1);dp[0] = 0;for(int i = 0; i <= amount; i ++){for(int coin : coins){if(i - coin < 0) continue;dp[i] = min(dp[i], dp[i - coin] + 1);}}return dp[amount] == amount + 1 ? -1 : dp[amount];}
};

还有一种视作完全背包的写法，一样的初始化和递推，将硬币视为物品，面值视为重量和价值，背包容量是amount
其中dp[j - coins[i]] != INT_MAX必不可少，因为如果其为INT_MAX的话，后序计算dp会+1，就会溢出

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i ++){//遍历物品for(int j = coins[i]; j <= amount; j ++){//遍历背包if(dp[j - coins[i]] != INT_MAX) dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

2.零钱兑换II

和零钱兑换一样，不一样的是这里要求返回硬币组合数。
可以视作完全背包做

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

这个题求的是组合，所以外层遍历背包，内存遍历物品。求组合数量的递推公式：dp[j]+=dp[j - coins[i]]
从这个递推式来看，初始化一定要有不为0的
dp[0] = 1，其他初始化为0

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for(int i = 0; i < coins.size(); i ++){for(int j = coins[i]; j <= amount; j ++){dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

3.面试题08.11.硬币

给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

dp[i]的含义是i分有几种表示方法，由于5,1和1,5不用特别区分，所以求的是组合数，外层遍历物品，内层遍历背包容量

当前硬币有取或者不取，取得话就是dp[i - coin]，不

class Solution {
public:const int mod = 1e9 + 7;int waysToChange(int n) {vector<int> dp(n + 1, 0);vector<int> coins = {1, 5, 10, 25};dp[0] = 1;for (int coin : coins) {for (int i = coin; i <= n; i++) {dp[i] = (dp[i] + dp[i - coin]) % mod;}}return dp[n];}
};

4.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

单词就是物品，字符串就是背包，因为物品可以重复填背包，所以这是个完全背包问题！
dp[i]：表示下标为0~i - 1的字符串可以被拆分为一个或多个在字典中出现的单词。
如果dp[j] == true且[j，i)出现在字典中了，那么dp[i] 也为 true，这句话记住基本就做出来了
本题求的是排列数，因为applepen是apple+pen的组合而不是pen+apple的组合

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size(), false);unordered_set<string> word(wordDict.begin(), wordDict.end());dp[0] = true;for(int i = 1; i <= s.size(); i ++){for(int j = 0; j < i; j ++){if(dp[j] && word.find(s.substr(j, i - j)) != word.end()) dp[i] = true;}}return dp[s.size()];}
};

5.最长递增子序列

输入一个无序的整数数组，请你找到其中最长的严格递增子序列的长度。
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。

dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
那么base case就是dp[0] = 1
以下是完整代码，其中res初始化为 1 至关重要。
如果 res 初始化为 0，而数组是递减的，那么 res 将永远保持 0，因为没有任何 dp[j] 会大于 1，所以内部循环的条件 if(res < dp[j]) 永远不会满足。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {//dp[i]是到nums[i]截止的vector<int> dp(nums.size() + 1, 1);int result = 1;for(int i = 1; i < nums.size(); i ++){for(int j = 0; j < i; j ++){if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);if(result < dp[i]) result = dp[i];}}return result;}
};

6.最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。

dp[i]：最长递增序列的长度
cnt[i]：最长递增序列的个数
设nums的最长上升子序列的长度为maxLen，那么答案为所有满足dp[i] = maxLen的 i 对应的cnt[i]之和
我们从小到大计算 dp数组的值，在计算 dp[i]之前，我们已经计算出 dp[0…i−1]的值，则状态转移方程为：
dp[i]=max⁡(dp[j])+1,其中 0≤j<i 且 num[j]<num[i]
即考虑往 dp[0…i−1]中最长的上升子序列后面再加一个 nums[i]。
由于 dp[j] 代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列，所以如果能从 dp[j] 这个状态转移过来，那么 nums[i] 必然要大于 nums[j]，才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列。

对于 cnt[i]，其等于所有满足 dp[j] + 1 = dp[i] 的 cnt[j]之和。在代码实现时，我们可以在计算 dp[i]的同时统计 cnt[i]的值。

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n), cnt(n);int ans = 0, maxLen = 0;for(int i = 0; i < n; ++i) {dp[i] = 1; // 初始化为1cnt[i] = 1; // 初始化为1for(int j = 0; j < i; ++j) {if(nums[i] > nums[j]) {if(dp[j] + 1 > dp[i]) {  //相当于 dp[i] = max(dp[j]+1, dp[i]);dp[i] = dp[j] + 1;cnt[i] = cnt[j];}else if(dp[j] + 1 == dp[i]){ //dp[j]+1 == dp[i] 有相同的长度cnt[i] += cnt[j];}}}if(dp[i] > maxLen) {maxLen = dp[i];ans = cnt[i];} else if(dp[i] == maxLen) {ans += cnt[i];}}cout << ans << endl;return ans;}
};

7.得到山形数组的最少删除次数

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3
• 存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：

arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]

给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

可以两部分处理这个问题：

1. 寻找所有可能的递增序列的最长长度。
2. 寻找所有可能的递减序列的最长长度。

1可以使用类似于最长递增子序列（LIS）的算法来实现。
2可以使用类似于最长递减子序列（LDS）的算法来实现。
对于每个位置 i，可以计算它作为山峰的情况下的最长山形子序列的长度，并求取最大的长度。然后，从总长度中减去这个最大长度就是最少删除次数。

class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {int n = nums.size();if(n < 3) return 0;//记录上升子序列vector<int> dp(n, 1);for(int j = 1; j < n; j ++){for(int i = 0; i < j; i ++){if(nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);}}//记录下降子序列vector<int> dp2(n, 1);for(int j = n - 2; j >= 0; j --){for(int i = n - 1; i > j; i --){if(nums[j] > nums[i]) dp2[j] = max(dp2[j], dp2[i] + 1);}}//找到了最长的山行子序列的长度int maxLen = 0;//以中心为基准for(int i = 1; i < n - 1; i ++){if(dp[i] > 1 && dp2[i] > 1) maxLen = max(maxLen, dp[i] + dp2[i] - 1);}return n - maxLen;}
};

8.最长公共子序列

text1和text2，返回最长处公共子序列的长度

dp[i][j]表示text1下标0~i-1和text2下标0 ~ j-1最长公共子序列的长度
所以dp的长度需要是len+1
text1[i - 1] == text2[j - 1]，dp[i][j] = dp[i - 1][j - 1] + 1
text1[i - 1] != text2[j - 1]，dp[i][j] = max(dp[i][j - 1]，dp[i - 1][j])

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int len1 = text1.size();int len2 = text2.size();vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));int res = 0;for(int i = 1; i <= len1; i ++){for(int j = 1; j <= len2; j ++){if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);if(res < dp[i][j]) res = dp[i][j];}}return res;}
};

9.最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

dp[i][j] 的含义是，nums1以下标i - 1结尾的子数组和nums2以下标j - 1结尾的子数组重复的最长子数组长度

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();int result = 0;vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for(int i = 1; i <= len1; i ++){for(int j = 1; j <= len2; j ++){if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;if(result < dp[i][j]) result = dp[i][j];}}return result;}
};

10.最长等差数列

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

dp[i][j]：以nums[i]结尾的子序列中，差值是j的最长等差数列长度
nums[i] - nums[j] = diff
dp[i][diff] = dp[j][diff] + 1
res实时变化

另外，由于0 <= nums[i] <= 500，所以diff在-500到500之间，又由于索引不可为负数，所以diff应该加500，变成0到1000间

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(1001, 1));int res = dp[0][0];for(int i = 0; i < n; i ++){for(int j = 0; j < i; j ++){int diff = nums[i] - nums[j] + 500;dp[i][diff] = dp[j][diff] + 1;res = max(res, dp[i][diff]);}}return res;}
};

11.最大子数组和

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

注意初始化，res需要初始为dp[0]

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

12.最长的斐波那契子序列的长度

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
eg：
输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
dp[i][j] 表示以 arr[i] 和 arr[j] 作为最后两个数字的最长斐波那契式子序列的长度。

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();unordered_map<int, int> indexMap;for (int i = 0; i < n; i++) {indexMap[arr[i]] = i;}vector<vector<int>> dp(n, vector<int>(n, 2));int maxLen = 0;for (int j = 1; j < n; j++) {for (int i = 0; i < j; i++) {int k = indexMap.find(arr[j] - arr[i]) != indexMap.end() ? indexMap[arr[j] - arr[i]] : -1;if (k >= 0 && k < i) {dp[i][j] = dp[k][i] + 1;maxLen = max(maxLen, dp[i][j]);}}}return maxLen > 2 ? maxLen : 0;}
};

13.最大正方形

在一个由0和1组成的二维矩阵内，找到只包含1的最大正方形，并返回其面积

前缀和做法：
和美团2024春招第一题平衡矩阵很像，给一个和平衡矩阵一样的做法
需要注意的是，在小美的平衡矩阵中，输入数组都是下标1开始，这里的matrix是从0开始的，而前缀和又必须从1开始，所以前缀和s要加的matrix[i - 1][j - 1] - ‘0’
左上角i，j的起始，已经是在前缀和s里面看了，所以从1开始而不是0

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {if (matrix.empty()) return 0;int m = matrix.size(), n = matrix[0].size();vector<vector<int>> s(m+1, vector<int>(n+1, 0));int res = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {s[i][j] = (matrix[i-1][j-1] - '0') + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}}// i 和 j 是左上角, l 和 r 是右下角// len 是正方形边长for (int len = 1; len <= min(m, n); len++) {for (int i = 1; i <= m - len + 1; i++) {for (int j = 1; j <= n - len + 1; j++) {int l = i + len - 1;int r = j + len - 1;int total = s[l][r] - s[l][j - 1] - s[i - 1][r] + s[i - 1][j - 1];if (total == len * len) res = max(res, len * len);}}}return res;}
};

动态规划做法：

1. dp[i][j] 代表(i，j)为右下角，且只包含1的正方形的边长最大值。
2. 递推公式：

• 如果该位置是0，则dp[i][j] = 0，因为当前位置不可能由1组成的正方形中
• 如果该位置是1，则dp[i][j]的值由其上方、左方和左上方的三个相邻位置的dp值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

3. 如果 i 和 j 中至少有一个为0，则位置(i，j)为右下角的最大正方形的边长只能是1，dp[i][j] = 1

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {if(matrix.empty()) return 0;int m = matrix.size();int n = matrix[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));int len = 0;for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(matrix[i][j] == '1'){if(i == 0 || j == 0) dp[i][j] = 1;else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;if(dp[i][j] > len) len = dp[i][j];}}}return len * len;}
};

14.最长有效括号

给一个字符串只包含 ‘(’ 和 ‘)’ ，找出最长有效括号子串。

dp[i]的含义是以下标1结尾的字符串最长有效括号子串的长度
所以上图dp[1] = 2， dp[3] = 4

1. 如果当前遍历到了‘(’，那么一定是非法序列，dp[i] = 0
2. 如果当前遍历到了‘)’，那么分2种情况

• ）的前面是（，那么dp[i] = dp[i - 2] + 2
• ）的前面是），那么需要检查i - dp[i - 1] - 1，即前一个合法序列的前一个位置是不是左括号，类似于图中的dp[7]，index = 7 的时候，此时 index - 1 也是右括号，我们需要知道 i - dp[i - 1] - 1 = 7 - dp [ 6 ] - 1 = 4 位置的括号的情况。而刚好 index = 4 的位置是左括号，此时 dp [ i ] = dp [ i - 1 ] + dp [ i - dp [ i - 1] - 2 ] + 2 （当前位置的前一个合法序列的长度，加上匹配的左括号前边的合法序列的长度，加上新增的长度 2）

class Solution {
public:int longestValidParentheses(string s) {vector<int> dp(s.size(), 0);int res = 0;for(int i = 1; i < s.size(); i ++){if(s[i] == ')'){if(s[i - 1] == '('){dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;}else if(i > 0 && i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '('){dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}}res = max(res, dp[i]);}return res;}
};

15.乘积最大子数组

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组，并将乘积返回
dpMax[i] 表示以第 i 个元素的结尾的子数组，乘积最大的值

1. 当nums[i] >= 0 并且dpMax[i - 1] > 0，dpMax[i] = dpMax[i - 1] * nums[i]
2. 当nums[i] >= 0 并且dpMax[i - 1] < 0，dpMax[i] = nums[i]
3. 当nums[i] < 0时，dpMax需要分情况讨论

• 当dpMin[i - 1] < 0，dpMax[i] = dpMin[i - 1] * nums[i]
• 当dpMin[i - 1] >= 0，dpMax[i] = nums[i]

上面引入了dpMin数组，怎么求dpMin和dpMax其实是一样的。
首先
dpMax[i] = max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);
求 dpMin[i] 同理
dpMin[i] = min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);
由于都是上一个dpMax或者上一个dpMin推导的，所以可以不设数组
dpMax = max(dpMin * nums[i], max(dpMax * nums[i], (double)nums[i]));
dpMin = min(dpMin * nums[i], min(preMax * nums[i], (double)nums[i]));
如果是int的话会有一个测试用例过不了

class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}double dpMax = nums[0];double dpMin = nums[0];double maxProd = nums[0];for (int i = 1; i < n; i++) {// 更新dpMin的时候需要dpMax之前的信息，所以先保存起来double preMax = dpMax;dpMax = max(dpMin * nums[i], max(dpMax * nums[i], (double)nums[i]));dpMin = min(dpMin * nums[i], min(preMax * nums[i], (double)nums[i]));maxProd = max(maxProd, dpMax);}return (int)maxProd; // 将结果转换回int，假设最终结果适合int类型。}
};

16.可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。

dp[i][j]：处理前i个元素，余数为j的最大和。j有三种可能0,1,2按照定义，最终答案就是dp[n][0]
对于nums[i - 1]，可选可不选

1. 如果nums[i - 1]%3 = 0，那么说明加入当前nums[i - 1]不会改变其余数，所以：

• dp[i][0] = max{dp[i - 1][0]，dp[i - 1][0] + nums[i - 1]}
• dp[i][1] = max{dp[i - 1][1]，dp[i - 1][1] + nums[i - 1]}
• dp[i][2] = max{dp[i - 1][2]，dp[i - 1][2] + nums[i - 1]}

2. 如果nums[i - 1]%3 = 1，那么说明加入当前nums[i - 1]之后，原来余数0会变成1，1变成2，2变成0

• dp[i][0] = max{dp[i - 1][0]，dp[i - 1][2] + nums[i - 1]}
• dp[i][1] = max{dp[i - 1][1]，dp[i - 1][0] + nums[i - 1]}
• dp[i][2] = max{dp[i - 1][2]，dp[i - 1][1] + nums[i - 1]}

3. 如果nums[i − 1]%3 = 2，那么说明加入当前nums[ i − 1]之后，原来的余数0会变成2，1变成 0，2变成1：

• dp[i][0] = max{dp[i - 1][0]，dp[i - 1][1] + nums[i - 1]}
• dp[i][1] = max{dp[i - 1][1]，dp[i - 1][2] + nums[i - 1]}
• dp[i][2] = max{dp[i - 1][2]，dp[i - 1][0] + nums[i - 1]}

class Solution {
public:int maxSumDivThree(vector<int>& nums) {int n = nums.size();int dp[n + 1][3];// dp[i][j]代表下标0~i-1的数中,÷3余数为j的最大和memset(dp,0,sizeof dp);dp[0][1] = -1e9 , dp[0][2] = -1e9;// dp[0][0]是前0个数。÷3余数为0的最大和,是0for(int i = 1;i <= n;i++){int r = nums[i - 1] % 3;if(r == 0){dp[i][0] = max(dp[i - 1][0] , dp[i - 1][0] + nums[i - 1]);dp[i][1] = max(dp[i - 1][1] , dp[i - 1][1] + nums[i - 1]);dp[i][2] = max(dp[i - 1][2] , dp[i - 1][2] + nums[i - 1]);}else if(r == 1){dp[i][0] = max(dp[i - 1][0] , dp[i - 1][2] + nums[i - 1]);dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + nums[i - 1]);dp[i][2] = max(dp[i - 1][2] , dp[i - 1][1] + nums[i - 1]);}else{dp[i][0] = max(dp[i - 1][0] , dp[i - 1][1] + nums[i - 1]);dp[i][1] = max(dp[i - 1][1] , dp[i - 1][2] + nums[i - 1]);dp[i][2] = max(dp[i - 1][2] , dp[i - 1][0] + nums[i - 1]);}}return dp[n][0];}
};

17.回文子串数目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

如果设置 dp[i] 的意义是指以下标 i 结尾的字符串有 dp[i] 个回文串，那就会很难想，因为dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系
所以应该这样设置：bool类型dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
假设s[i] != s[j]，不是回文子串
s[i] == s[j]，j - i <= 1，是回文串(a或aa的情况)，如果 i 和 j 差距大于1，就撤回一步看dp[i + 1][j - 1]是不是回文子串

注意初始化，第二个for的j要从i开始不是i+1，差一步都不行

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int res = 0;for(int i = s.size() - 1; i >= 0; i --){for(int j = i; j < s.size(); j ++){if(s[i] == s[j]){if(j - i <= 1){res++;dp[i][j] = true;}else{if(dp[i + 1][j - 1]){res++;dp[i][j] = true;}}}}}return res;}
};

18.最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。
子序列，所以可以不连续

大致逻辑和3一样
在s[i] == s[j]时，dp[i][j] = dp[i + 1][j - 1] + 2
在s[i] != s[j]时，加入s[j]的回文子序列长度为dp[i + 1][j]。加入s[i]的回文子序列长度为dp[i][j - 1]。

从递推式可以看出来，i == j的情况没有覆盖，所以需要初始化为1

另外加入s长度只有一个的话，无法进入for循环，这个时候应该输出1，所以res也需要初始化为1

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));int res = 1;for(int i = 0; i < s.size(); i ++) dp[i][i] = 1;for(int i = s.size() - 1; i >= 0; i --){for(int j = i + 1; j < s.size(); j ++){if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);if(dp[i][j] > res) res = dp[i][j];}}return res;}
};

19.最长回文子串

给你一个字符串 s，找到 s 中最长的 回文子串。
和3差不多

class Solution {
public:string longestPalindrome(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int l = 0, maxLen = -1;for(int i = s.size() - 1; i >= 0; i --){for(int j = i; j < s.size(); j ++){if(s[i] == s[j]){if(j - i <= 1) dp[i][j] = true;else if(dp[i + 1][j - 1]) dp[i][j] = true;}if(dp[i][j] && j - i + 1 > maxLen){maxLen = j - i + 1;l = i;}}}        return s.substr(l, maxLen);}
};

20.买卖股票的最佳时机

给prices数组，只能买卖一次！
0持有，1不持有
注意：只能买一次，状态不能从dp[i-1][1]转移，所以只有-prices[i]，如果不限次数就可以写dp[i - 1][1] - prices[i]了!!!

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

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

无限次买卖，卖出同时需要付一笔手续费

因为是无限次买卖，所以状态从dp[i-1][1]转移，不限次数写成dp[i - 1][1] - prices[i]
买的时候减去fee

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));//0持有,1不持有dp[0][0] = -prices[0];for(int i = 1; i < prices.size(); 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[prices.size() - 1][1];}
};

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

限制最多可以完成两笔交易

class Solution {
public:int maxProfit(vector<int>& prices) {//0第一次持有,1第一次不持有,2第二次持有,3第二次不持有vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = -prices[0];dp[0][2] = -prices[0];for(int i = 1; i < prices.size(); i ++){dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);}return dp[prices.size() - 1][3];}
};

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

最多可以完成k笔交易，也就是说，最多可以买k次，卖k次

k从1开始，分奇偶

class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2*k + 1, 0));//奇数持有，偶数不持有for(int i = 1; i < 2*k + 1; i ++){if(i % 2 == 1) dp[0][i] = -prices[0];}for(int i = 1; i < prices.size(); i ++){for(int j = 1; j <= 2*k - 1; j += 2){dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

24.打家劫舍

给定一个代表每个房屋存放金额的非负整数数组，相邻房屋装有相互连通的防盗系统，求最多偷的金额。
关键函数： dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

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

25.打家劫舍II

房屋围城一圈，最后一个房屋和第一个房屋紧邻，偷相邻房间会自动报警

1. 考虑不包含首尾元素
2. 考虑包含首元素不包含尾元素
3. 考虑不包含首元素包含尾元素
   考虑是包含但不一定要选，所以情况23包含了1
   简单点来说，考虑偷第一个不偷第二个和偷第二个不偷第一个的情况
   两个情况取最值，单领一个情况的计算就和I一样

class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if(len == 0) return 0;if(len == 1) return nums[0];if(len == 2) return max(nums[0], nums[1]);int result1 = robRange(nums, 0, len - 2);int result2 = robRange(nums, 1, len - 1);int result = max(result1, result2);return result;}int robRange(vector<int>& nums, int start, int end){vector<int> dp(nums.size() + 1, 0);dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for(int i = start + 2; i <= end; i ++){dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end];}
};

26.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
关键代码：
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));for(int i = 0; i < m; i ++) dp[i][0] = 1;for(int i = 0; i < n; i ++) dp[0][i] = 1;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];}
};

27.不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

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

28.最小路径和

给定一个包含非负整数的m * n网格grid，找出一条从左上角到右下角的路径，使得路径上的数字总和最小。

注意边界问题，第一行第一列需要初始化，所有for都是从1开始的

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

29.三角形的最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

题目的意思，在相邻节点的条件下，求最小路径，与(i, j)点相邻的结点为(i + 1, j)和 (i + 1, j + 1)

第 i 行的第 j 个元素从哪里来？可以从第 i - 1 行第 j 或第 j - 1 个元素下落过来。
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]

注意边界！！！dp[i][0]必须初始化，dp[0][i]不用，因为dp[0][i]一定只有一个，毕竟三个三角形

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

30.两个字符串的删除操作

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

dp[i][j]：以i-1为结尾的字符串word1，和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

1. 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1]
2. 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

• 删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
• 删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
• 删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size();int len2 = word2.size();vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for(int i = 0; i <= len1; i ++) dp[i][0] = i;for(int i = 0; i <= len2; i ++) dp[0][i] = i;for(int i = 1; i <= len1; i ++){for(int j = 1; j <= len2; j ++){if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] =  min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}return dp[len1][len2];}
};

31.编辑距离

可以对一个单词进行增加，删除和替换，现有两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

dp[i][j]表示以下标i-1结尾的字符串word1，和以下标j-1结尾的字符串word2，最近编辑距离为dp[i][j]，所以i，j最大都可以达到len

1. word[i - 1] == word2[j - 1]的时候不操作，dp[i][j]=dp[i-1][j-1]
2. word1[i - 1] ！= word2[j - 1]的时候操作，分三种情况，增删换

• 增加/删除：word1增加一个元素，相当于word2减少一个元素。比如word1 = “a”，word2 = “ab”，word1增加一个元素b和word2删除一个元素b的操作数是一样的；word1减少一个元素，相当于word2增加一个元素，比如word1 = “ab”，word2 = “a”，word1减少一个b和word2增加一个b用的操作数是一样的。所以dp[i][j] = dp[i][j - 1] + 1
• 替换：dp[i][j] = dp[i - 1][j - 1] + 1

class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size();int len2 = word2.size();vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for(int i = 0; i <= len1; i ++) dp[i][0] = i;for(int i = 0; i <= len2; i ++) dp[0][i] = i;for(int i = 1; i <= len1; i ++){for(int j = 1; j <= len2; j ++){if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));}}return dp[len1][len2];}
};

32.一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

背包有2个维度，m个0和n个1属于背包，strs数组是物品，由于物品只能选一次，所以这是个01背包问题
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i] [j]。
递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(string str : strs){//遍历物品int zoreNums = 0;int oneNums = 0;for(int i = 0; i < str.size(); i ++){if(str[i] == '0') zoreNums ++;else oneNums ++;}for(int j1 = m; j1 >= zoreNums; j1 --){//遍历背包，两个维度for(int j2 = n; j2 >= oneNums; j2 --){dp[j1][j2] = max(dp[j1][j2], dp[j1 - zoreNums][j2 - oneNums] + 1);}}}return dp[m][n];}
};

33.目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

sum_pos - sum_neg = sum
sum_pos + sum_neg = target
所以：sum_pos = (target + sum) % 2
01背包问题

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int i = 0; i < nums.size(); i ++) sum += nums[i];if((target + sum) % 2 != 0) return 0;if(abs(target) > sum) return 0;int sum_pos = (target + sum) / 2;// 背包是sum_pos,nums中的值是物品,只能使用一次，是0-1背包vector<int> dp(sum_pos + 1, 0);dp[0] = 1;for(int i = 0; i < nums.size(); i ++){for(int j = sum_pos; j >= nums[i]; j --){dp[j] += dp[j - nums[i]];}}return dp[sum_pos];}
};

34.分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

一个子集的大小就除2，这就是背包容量，nums里面的元素是物品，由于每个元素只能用一次，所以是01背包

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int i = 0; i < nums.size(); i ++){sum += nums[i];}if(sum % 2 != 0) return false;int target = sum / 2;//初始化vector<int> dp(target + 1, 0);for(int i = 0; i < nums.size(); i ++){for(int j = target; j >= nums[i]; j --){dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}if(dp[target] == target) return true;return false;}
};

35.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例：

• 输入：n = 12
• 输出：3
• 解释：12 = 4 + 4 + 4

平方数就是物品，并且可以无限次使用，n是背包容量，现在问凑满这个背包最少需要多少物品
dp[j] = min(dp[j]，dp[j - i * i] + 1)

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for(int i = 1; i * i<= n; i ++){//物品for(int j = i * i; j <= n; j ++){//背包dp[j] = min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
};

36.比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

有一个极其巧妙的做法：
偶数的二进制1个数超级简单，因为偶数相当于是被更小的某个数乘2，这个乘2在二进制中的体现就是整体左移，比如数字1的二进制是1，左移是10，就是2。所以1的个数是不变的，只是多了个0，dp[i] = dp[i / 2]
奇数就更简单了，奇数由不大于数的偶数+1，偶数+1在二进制上会发生什么？就是某位加1，所以dp[i] = dp[i / 2] + 1

class Solution {
public:vector<int> countBits(int n) {int i = 1;vector<int> dp(n + 1, 0);for(int i = 0; i <= n; i ++){if(i % 2 == 0) dp[i] = dp[i / 2];else dp[i] = dp[i - 1] + 1;}return dp;}
};

37.石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

用二维数组 dp[i][j] 记录 piles[i] ~ piles[j] 序列中，先选择的人可以获得比对手多的石子数量。

1. 若选择piles[i]，则对手可选的范围变为piles[i + 1] ~ piles[j]，选择piles[i]后，先手变成后手，对手可选择的石子数量为dp[i + 1][j]，则我们比对手多的石子的数量记为dp[i][j] = piles[i] - dp[i + 1][j]。
2. 若选择piles[j],则对手可选的范围变为 piles[i]~piles[j-1] ，选择piles[j]后，我们变为后手，所以对手可选择的比我们多的石子的数量为 dp[i][j-1]，则我们比对手多的石子的数量记为dp[i][j] = piles[j]- dp[i][j-1]。

所以 dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
遍历是从小范围到大范围，为了保证每次计算依赖的值已经被计算过，应该先遍历数组长度len，再遍历l和r

class Solution {
public:bool stoneGame(vector<int>& piles) {int n = piles.size();vector<vector<int>> dp(n, vector<int>(n, 0));for(int i = 0; i < n; i++) {dp[i][i] = piles[i];}for (int len = 2; len <= n; len++) {for (int l = 0; l <= n - len; l++) {int r = l + len - 1;dp[l][r] = max(piles[l] - dp[l + 1][r], piles[r] - dp[l][r - 1]);}}return dp[0][n - 1] > 0;}
};

38.预测赢家

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

和石子游戏区别不大

class Solution {
public:bool predictTheWinner(vector<int>& nums) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(n, 0));for (int i = 0; i < n; i++) dp[i][i] = nums[i];for (int len = 2; len <= n; len++) {for (int l = 0; l <= n - len; l++) {int r = l + len - 1; // r是右端点dp[l][r] = max(nums[l] - dp[l + 1][r], nums[r] - dp[l][r - 1]);}}return dp[0][n - 1] >= 0;}
};

39.不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

dp[i]表示i个节点的二叉搜索树共有多少种
确定递推公式，先观察dp[3]怎么得出来的

dp[3]，就是元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

• 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
• 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
• 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

所以dp[i] += dp[j - 1] * dp[i - j]

初始化，空树也是二叉搜索树，dp[0] = 1

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;for(int i = 1; i <= n; i ++){for(int j = 1; j <= i; j ++){dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
};

40.解码方法

dp[i]表示以第i个字符为结尾，解码方法的总数

• s[i] 和 s[i - 1] 是单独为一个字符形成两个数字，那么dp[i]的值就是dp[i-1]的值；
• 如果 s[i] 和 s[i-1] 合并为一个字符形成为一个数字，那么 dp[i] 的值就是 dp[i-2] 的值。因为 s[i] 和 s[i-1] 都形成一个数字了，再 dp[i] 往前就是就是 dp[i-2] 了。
• 因为单独一个0不能解码，所以当s[i]和s[i-1]是单独为一个字符时，若s[i]==‘0’，dp[i] = 0
• 如果形成的2位数数字不在[10,26]区间内的话，所以当s[i]和s[i-1]合并为一个字符时，若超出这个范围了，dp[i] = 0

所以状态转移方程包含dp[i-1]和dp[i-2]
那么需要初始化dp[0]和dp[1]
dp[0]只需要判断他是不是0，即可得出结论
dp[1]的话有两种情况，合为一个数；分开成两个数。合为一个数需要判断形成的这一个数是否在[10, 26]这个范围里面；分别为两个数只需要判断s[0]和s[1]是不是都不为’0’。

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

41.鸡蛋掉落

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

没有鸡蛋个数的限制的话，肯定是二分法效率最高
有鸡蛋限制的话，先留一个鸡蛋，其他二分法或者是多分法，找到鸡蛋碎的区间，在拿最后一个鸡蛋逐步试楼层

dp[k][n] 表示有 k 个鸡蛋和 n 层楼时，最少的扔鸡蛋次数。
状态转移方程：对于每个楼层 i，我们考虑两种情况：
鸡蛋碎了，问题转化为 k-1 个鸡蛋和 i-1 层楼的问题。
鸡蛋没碎，问题转化为 k 个鸡蛋和 n-i 层楼的问题。
取两者中的最大值，然后加 1，表示在第 i 层扔鸡蛋所需的最少次数。

class Solution {
public:int superEggDrop(int K, int N) {// dp[i][j] 表示 i 个鸡蛋，j 层楼时的最少尝试次数vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));// 初始化 base case// 如果只有一个鸡蛋，只能线性扫描，每层楼都要试，最坏情况的次数就是最少次数for (int j = 1; j <= N; j++) {dp[1][j] = j;}for (int i = 2; i <= K; i++) {for (int j = 1; j <= N; j++) {int left = 1, right = j;int res = INT_MAX;// 二分搜索，优化线性扫描while (left <= right) {int mid = (left + right) / 2;int broken = dp[i - 1][mid - 1];int notBroken = dp[i][j - mid];// 在最坏情况下的最少尝试次数if (broken > notBroken) {right = mid - 1;res = min(res, broken + 1);} else {left = mid + 1;res = min(res, notBroken + 1);}}dp[i][j] = res;}}// 答案在 dp[K][N] 中return dp[K][N];}
};

42.正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘※’ 的正则表达式匹配。

• ‘.’匹配任意单个字符
• ‘※’匹配零个或多个前面的那一个元素
  
  s 和 p 相互匹配的过程大致是，两个指针 i, j 分别在 s 和 p 上移动，如果最后两个指针都能移动到字符串的末尾，那么就匹配成功，反之则匹配失败。
  其实.很好匹配，遇到.无脑匹配就可以了，但是 ※ 很厉害了，他可以让之前的那个字符重复任意次数，包括0次，意味着这个是空字符串也没事。“.a※b”可以匹配文本“zaaab”，也可以匹配“cb”。而模式串“ .※ ”更厉害了，他可以匹配任何文本，包括空字符串。

如果i到了s的末尾，j没有到p的末尾，这时候就要考虑p剩余的元素能否匹配空字符串。什么能匹配空字符串呢？

• ‘.’不行，因为 ‘.’ 自身并不意味着可以选择不匹配任何字符。它总是匹配一个字符，无论是字母、数字还是符号。因此，. 不能单独用来表示“匹配空字符串”的意思。
• ‘ * ’用于指定其前一个字符可以出现 0 次、1 次或多次。它的关键在于 * 可以让前面的字符出现次数为零，这就意味着完全可以不匹配任何字符。

现在开始一步一步写代码，如果不考虑※通配符，面对两个待匹配字符s[i]和p[j]，我们唯一能做的就是考虑她俩是否匹配。

bool isMatch(string s, string p){int i = 0, j = 0;while(i < s.size() && j < p.size()){if(s[i] == p[j] || p[j] == '.'){i ++; j ++;}else{return false;}}return i == j;
}

如果加入 ※ 匹配符，局面就会复杂一些。
当p[j + 1] 为 ※ 通配符时，分情况讨论：

1. 如果s[i] == p[j]，那么有两种情况：

• p[j] 有可能会匹配多个字符，比如 s = “aaa”, p = “a*”，那么 p[0] 会通过 * 匹配 3 个字符 “a”。
• p[i] 也有可能匹配 0 个字符，比如 s = “aa”, p = “a*aa”，由于后面的字符可以匹配 s，所以 p[0] 只能匹配 0 次。

2. 如果 s[i] != p[j]，只有一种情况：

• p[j] 只能匹配 0 次，然后看下一个字符是否能和 s[i] 匹配。比如说 s = “aa”, p = “b*aa”，此时 p[0] 只能匹配 0 次。

if(s[i] == p[j] || p[j] == '.'){//匹配if(j < p.size() - 1 && p[j + 1] == '*'){// 有 * 通配符，可以匹配 0 次或多次} else {// 无 * 通配符，老老实实匹配 1 次i ++; j ++;}
}else{// 不匹配if(j < p.size() - 1 && p[j + 1] == '*'){// 有 * 通配符，只能匹配0}else{// 无 * 通配符，匹配无法进行下去了return false;}
}

定义dp函数bool dp(string s, int i, string p, int j)
若 dp(s, i, p, j) = true，则表示 s[i…] 可以匹配 p[j…]；若 dp(s, i, p, j) = false，则表示 s[i…] 无法匹配 p[j…]。

根据这个定义，我们想要的答案就是 i = 0, j = 0 时 dp 函数的结果：

bool dp(string s, int i, string p, int j) {if (s[i] == p[j] || p[j] == '.') {// 匹配if (j < p.size() - 1 && p[j + 1] == '*') {// 1.1 通配符匹配 0 次或多次// 先执行第一个再执行第二个return dp(s, i, p, j + 2) || dp(s, i + 1, p, j);} else {// 1.2 常规匹配 1 次return dp(s, i + 1, p, j + 1);}} else {// 不匹配if (j < p.size() - 1 && p[j + 1] == '*') {// 2.1 通配符匹配 0 次return dp(s, i, p, j + 2);} else {// 2.2 无法继续匹配return false;}}
}

解析：

1. 通配符匹配0次或多次dp(s, i, p, j + 2)
   将j加2，i不变，含义就是直接跳过p[j]和之后的通配符，即通配符匹配0次。
   即使s[i] == p[j]，依然可能出现匹配0次这种情况，如下图：
   
2. 匹配多次的情况dp(s, i + 1, p, j)
   将i加1，j不变，含义就是p[j]匹配了s[i]，但p[j]还可以继续匹配，即通配符匹配多次的情况。
   
3. 常规匹配1次。无 * 的常规匹配。如果 s[i] == p[j]，就是 i 和 j 分别加一。
4. 不等。通配符匹配0次。将j加2，i不变。
   
5. 不等且无*，匹配失败
   完整代码：

考这个我就去死(╯>д<)╯⁽˙³˙⁾

class Solution {
public:bool isMatch(string s, string p) {int m = s.size();int n = p.size();// dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));// 空字符串和空模式是匹配的dp[0][0] = true;// 处理 p 开头是 '*' 的情况for (int j = 1; j < n; j += 2) {if (p[j] == '*') {dp[0][j + 1] = dp[0][j - 1];} else {break;}}// 填充 dp 表格for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p[j - 1] == '*') {// '*' 可以匹配零个或多个字符dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));} else {// 逐字符匹配，或者 '.' 可以匹配任意字符dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');}}}// 最终结果return dp[m][n];}
};

43.通配符匹配

给你一个输入字符串 (s) 和一个字符模式 ( p) ，请你实现一个支持 ’ ? ’ 和 ’ * ’ 匹配规则的通配符匹配：

• ’ ? ’ 可以匹配任何单个字符。
• ’ * ’ 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

唯一需要注意的是本题的测试用例可能出现很多 * 连续出现的情况，很容易看出连续多个 * 和一个 * 的通配效果是一样的，所以我们可以提前删除连续的 * 以便提升一些效率。

class Solution {
public:bool isMatch(string s, string p) {int m = s.size();int n = p.size();// dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));// 空字符串和空模式是匹配的dp[0][0] = true;// 处理 p 开头是 '*' 的情况for (int j = 1; j <= n; ++j) {if (p[j - 1] == '*') {dp[0][j] = dp[0][j - 1];}}// 填充 dp 表格for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {// 单个字符匹配，或 '?' 匹配任意一个字符dp[i][j] = dp[i - 1][j - 1];} else if (p[j - 1] == '*') {// '*' 可以匹配零个或多个字符dp[i][j] = dp[i - 1][j] || dp[i][j - 1];}}}// 最终结果return dp[m][n];}
};

44.交错字符串

给定三个字符串s1，s2，s3，请你帮忙验证s3是否是由s1与s2交错组成的。

实则就是一个使用双指针技巧合并两个字符串的过程。
但本题跟普通的数组/链表双指针技巧不同的是，这里需要穷举所有情况。比如 s1[i], s2[j] 都能匹配 s3[k] 的时候，到底应该让谁来匹配，才能完全合并出 s3 呢？回答这个问题很简单，我不知道让谁来，那就都来试一遍好了。
所以本题肯定需要一个递归函数来穷举双指针的匹配过程，然后用一个备忘录消除递归过程中的重叠子问题，也就能写出自顶向下的递归的动态规划解法了。

class Solution {
private:vector<vector<int>> memo;bool dp(string& s1, int i, string& s2, int j, string& s3){// base caseint k = i + j;if(k == s3.size()) return true;if(memo[i][j] != -1) return memo[i][j] == 1;bool res = false;if(i < s1.size() && s1[i] == s3[k]) res = dp(s1, i + 1, s2, j, s3);if(j < s2.size() && s2[j] == s3[k]) res = res || dp(s1, i, s2, j + 1, s3);memo[i][j] = res ? 1 : 0;return res;}
public:bool isInterleave(string s1, string s2, string s3) {int m = s1.size(), n = s2.size();if(m + n != s3.size()) return false; // 长度不对的话，不可能对memo = vector<vector<int>>(m + 1, vector<int>(n + 1, -1));return dp(s1, 0, s2, 0, s3);}
};

这篇关于codetop标签动态规划大全C++讲解(上)！！动态规划刷穿地心！！学吐了家人们o(╥﹏╥)o的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---