C++ 动态规划

子序列子串相关

单个指一个数组或字符串，两个指两个数组或字符串。

最长上升子序列-单个

dp[i]：以下标i为结尾的递增的最长子序列长度。

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int sz=nums.size();// dp[i] i结尾的最长子序列长度// dp[i]=max(dp[i],dp[j]+1)vector<int> dp(sz,1);int res=1;for(int i=1;i<sz;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j])dp[i]=max(dp[j]+1,dp[i]);}res=max(res,dp[i]);}return res;}
};

最长上升子序列的个数-单个 

最长连续上升子序列-单个

dp[i]：以下标i为结尾的连续递增的子序列长度。

因为本题要求连续递增子序列，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。

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

最长重复连续子序列-两个

dp[i][j] ：以下标i - 1为结尾的A和以下标j - 1为结尾的B，最长重复子数组长度。

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

最长重复子序列-两个

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列。

主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

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

不相交的线🧵-两个

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。那么就和最长重复子序列一样了！

最大连续子序列的和-单个

具有最大和的连续子数组。

dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和.

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

dp[i] = max(dp[i - 1] + nums[i], nums[i]).

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

判断子序列-两个

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度

• if (s[i - 1] == t[j - 1])
  • t中找到了一个字符在s中也出现了
• if (s[i - 1] != t[j - 1])
  • 相当于t要删除元素，继续匹配

if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）

if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1]。

class Solution {
public:bool isSubsequence(string s, string t) {int sz1=s.size(),sz2=t.size();vector<vector<int>> dp(sz1+1,vector<int>(sz2+1));for(int i=1;i<=sz1;i++){for(int j=1;j<=sz2;j++){if(s[i-1]==t[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=dp[i][j-1];}}}return dp[sz1][sz2]==sz1;}
};

子序列出现的个数-两个?

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数。

回文子串的个数-单个

计算这个字符串中有多少个回文子串。

判断一个子字符串（字符串下标范围[i,j]）是否回文

                                               依赖于

子字符串（下标范围[i + 1, j - 1]）） 是否是回文

所以为了明确这种递归关系，dp数组是要定义成一个二维dp数组。

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果dp[i][j]为true，否则为false。

当s[i]与s[j]不相等，dp[i][j]一定是false。

当s[i]与s[j]相等时，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

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

最长回文子串-单个

class Solution {
public:string longestPalindrome(string s) {int len = 0;int start = 0;int sz = s.size();vector<vector<bool>> dp(sz, vector<bool>(sz));for (int i = sz - 1; i >= 0; i--) {for (int j = i; j < sz; j++) {if (s[i] == s[j]) {if (j - i < 2)dp[i][j] = true;elsedp[i][j] = dp[i + 1][j - 1];}if (dp[i][j]) {if (j - i + 1 > len) {start = i;len = j - i + 1;}}}}return s.substr(start,len);}
};

最长回文子序列-单个

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度

如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

class Solution {
public:int longestPalindromeSubseq(string s) {int sz=s.size();vector<vector<int>> dp(sz,vector<int>(sz));int res=1;for(int i=0;i<sz;i++)dp[i][i]=1;for(int i=sz-1;i>=0;i--){for(int j=i+1;j<sz;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]);res=max(res,dp[i][j]);}}return res;}
};

二维动态

不同路径

不同路径II

01背包🎒

有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。

如果改为滑动数组，则需倒序遍历背包容量，保证物品只被放进一次。

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

分割等和子集

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，装满容量为x的背包，有几种方法。求组合类问题的公式：

dp[j] += dp[j - nums[i]]

完全背包🎒

零钱兑换II

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

排列总和 

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的排列的个数。

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

完全平方数

完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品。

单词拆分

买卖股票