动态规划
139. 单词拆分
这题感觉好晕
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {//dp[i] 字符串长度为i，dp[i]为true表示可以拆分成字典中的一个或两个字符串//if(dp[j]是true,并且从j到i这个子串出现在字典中) dp[i]=true;//dp[0]=true;其余为false//先遍历含量，再遍历种类unordered_set<string> wordSet(wordDict.begin(),wordDict.end());vector<bool>dp(s.size()+1,false);dp[0]=true;for(int i=1;i<=s.size();i++){//背包for(int j=0;j<i;j++){//物品string word=s.substr(j,i-j);if(wordSet.find(word)!=wordSet.end()&&dp[j])dp[i]=true;}}return dp[s.size()];}
};56. 携带矿石资源（第八期模拟笔试）
#include<iostream>
#include<vector>
using namespace std;
int main(){int c,n;cin>>c>>n;vector<int>w(n);vector<int>v(n);vector<int>k(n);for(int i=0;i<n;i++){cin>>w[i];}for(int i=0;i<n;i++){cin>>v[i];}for(int i=0;i<n;i++){cin>>k[i];}//dp[j]容量为j的背包所装的最大价值为dp[j]//dp[j]=max(dp[j-w[i]]+v[i],dp[j]),//全部初始化为0//先遍历物品再遍历容量，容量倒序vector<int>dp(c+1,0);for(int i=0;i<n;i++){while(k[i]!=1){w.push_back(w[i]);v.push_back(v[i]);k[i]--;}}for(int i=0;i<w.size();i++){for(int j=c;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[c]<<endl;return 0;
}198. 打家劫舍
class Solution {
public:int rob(vector<int>& nums) {//dp[j] 从下标j及之前的屋子中获取的最大的价值为dp[j]//dp[j]=max(dp[j-1],dp[j-2]+nums[j])//dp[0]=nums[0],dp[1]=max(nums[0],nums[1])//从左到右遍历房屋 if(nums.size()==1) return nums[0]; vector<int>dp(nums.size(),0);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];}
};213. 打家劫舍 II
class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1) return nums[0];int res1=robRange(nums,0,nums.size()-2);int res2=robRange(nums,1,nums.size()-1);return max(res1,res2);}int robRange(vector<int>& nums,int start,int end){if(end==start)return nums[start];vector<int>dp(nums.size(),0);dp[start]=nums[start];dp[start+1]=max(nums[start+1],nums[start]);for(int i=start+2;i<=end;i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[end];}
};337. 打家劫舍 III
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int rob(TreeNode* root) {vector<int> res=robTree(root);return max(res[0],res[1]);}//长度为2的数组，0 不偷，1 偷vector<int> robTree(TreeNode* cur){if(cur==nullptr) return vector<int>{0,0};//后序遍历vector<int> left=robTree(cur->left);vector<int> right=robTree(cur->right);//偷cur,不偷左右孩子int val1=cur->val+left[0]+right[0];//不偷cur,那可以考虑偷左右孩子int val2=max(left[0],left[1])+max(right[0],right[1]);return vector<int>{val2,val1};}
};121. 买卖股票的最佳时机
class Solution {
public:int maxProfit(vector<int>& prices) {//dp[i][0] 持有股票所拥有的最大现金 dp[i][1]不持有股票所拥有的最大现金//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[0][0]=-prices[0],dp[0][1]=0;//从左到右遍历vector<vector<int>>dp(prices.size(),vector<int>(2));dp[0][0]=-prices[0],dp[0][1]=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]);}return dp[prices.size()-1][1];}
};版本二减少空间
class Solution {
public:int maxProfit(vector<int>& prices) {//dp[i][0] 持有股票所拥有的最大现金 dp[i][1]不持有股票所拥有的最大现金//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[0][0]=-prices[0],dp[0][1]=0;//从左到右遍历vector<vector<int>>dp(2,vector<int>(2));dp[0][0]=-prices[0],dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i%2][0]=max(dp[(i-1)%2][0],-prices[i]);dp[i%2][1]=max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i]);}return dp[(prices.size()-1)%2][1];}
};122. 买卖股票的最佳时机 II
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(prices.size(),vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=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]);}return dp[prices.size()-1][1];}
};版本二减少空间
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>>dp(2,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i%2][0]=max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);dp[i%2][1]=max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i]);}return dp[(prices.size()-1)%2][1];}
};123. 买卖股票的最佳时机 III
class Solution {
public:int maxProfit(vector<int>& prices) {//是可以当天卖了再当天买，当天买再当天卖这样操作符合题意 虽然很蠢，但是符合规矩，符合题意//dp[i][j]股票在第i天第j种状态下最大现金 j=0,无操作；j=1，第一次持有状态；j=2，第一次不持有状态；j=3,第二次持有状态；j=4,第二次不持有状态//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])//dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])//dp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;dp[0][3]=-prices[0];dp[0][4]=0;vector<vector<int>>dp(prices.size(),vector<int>(5));dp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;dp[0][3]=-prices[0];dp[0][4]=0;for(int i=1;i<prices.size();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]);dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[prices.size()-1][4];}
};188. 买卖股票的最佳时机 IV
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+=2){//奇数下标dp[0][i]=-prices[0];}for(int i=1;i<prices.size();i++){for(int j=0;j<2*k-1;j+=2){//这里是<2k-1，因为递推公式中下标是j+1,j+2//j为奇是持有dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);//j为偶是不持有dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}return dp[prices.size()-1][2*k];}
};309. 买卖股票的最佳时机含冷冻期
class Solution {
public:int maxProfit(vector<int>& prices) {//dp[i][j] 第i天第j种状态所获得的最大现金//dp[i][0] 买入股票状态 dp[i][1] 保持卖出状态 dp[i][2]今天卖出 dp[i][3] 冷冻期状态 //dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i])//dp[i][1]=max(dp[i-1][1],dp[i-1][3])//dp[i][2]=dp[i-1][0]+prices[i] dp[i][3]=dp[i-1][2]//dp[0][0]=-prices[0] dp[0][1]=0 dp[0][2]=0 dp[0][3]=0vector<vector<int>>dp(prices.size(),vector<int>(4,0));dp[0][0]=-prices[0];for(int i=1;i<prices.size();i++){dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][3]);dp[i][2]=dp[i-1][0]+prices[i];dp[i][3]=dp[i-1][2];}int res=max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));return res;}
};714. 买卖股票的最佳时机含手续费
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {//dp[i][0]持有股票 dp[i][1]不持有股票//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)vector<vector<int>>dp(prices.size(),vector<int>(2,0));dp[0][0]=-prices[0];dp[0][1]=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];}
};300. 最长递增子序列
class Solution {
public:int lengthOfLIS(vector<int>& nums) {//dp[i] 下标从0到i中以dp[i]结尾的最长递增子序列的长度//if(dp[i]>dp[j])dp[i]=max(dp[i],dp[j]+1)//全初始化为1//从前往后遍历if(nums.size()==1) return 1;vector<int>dp(nums.size(),1);int res=INT_MIN;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);}res=max(dp[i],res);}return res;}
};674. 最长连续递增序列
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};718. 最长重复子数组
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {//dp[i][j] 以i-1结尾的A数组和以j-1结尾的B数组公共的，长度最长的子数组的长度为dp[i][j]//dp[i][j]=dp[i-1][j-1]+1//dp[0][j]和dp[i][0]都初始化为0//双层遍历vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));int res=0;for(int i=1;i<=nums1.size();i++){for(int j=1;j<=nums2.size();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;}
};1143. 最长公共子序列
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {//dp[i][j]A数组下标从0~i-1和B数组下标从0~j-1的最长公共子序列长度为dp[i][j]//dp[i][j]=dp[i-1][j-1]+1或dp[i][j]=max(dp[i-1][j],dp[i][j-1])//全部初始化为0//从上往下从左往右vector<vector<int>>dp(text1.size()+1,vector<int>(text2.size()+1,0));for(int i=1;i<=text1.size();i++){for(int j=1;j<=text2.size();j++){if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[text1.size()][text2.size()];}
};1035. 不相交的线
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));for(int i=1;i<=nums1.size();i++){for(int j=1;j<=nums2.size();j++){if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[nums1.size()][nums2.size()];}
};53. 最大子数组和
class Solution {
public:int maxSubArray(vector<int>& nums) {//dp[i] 下标从0~i的具有最大和的连续子数组的最大和为dp[i]//dp[i]=max(dp[i-1]+nums[i],nums[i]);//dp[0]初始化为nums[0]，其他的无所谓vector<int>dp(nums.size(),0);dp[0]=nums[0];int res=dp[0];for(int i=1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);res=max(res,dp[i]);}return res;}
};392. 判断子序列
class Solution {
public:bool isSubsequence(string s, string t) {//dp[i][j] 以i-1结尾的A数组和以j-1结尾的B数组的最长子序列长度 //dp[i][j]=dp[i-1][j-1]+1 dp[i][j]=dp[i][j-1]//全部初始化为0 vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();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];}}bool res;if(dp[s.size()][t.size()]==s.size()) return true;else return false;}
};115. 不同的子序列
class Solution {
public:int numDistinct(string s, string t) {//dp[i][j]以i-1结尾的s数组的子序列中出现以j-1结尾的t数组的个数//dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 或者dp[i][j]=dp[i-1][j]//dp[i][0]初始化为1，其他初始化为0vector<vector<unsigned long long int>>dp(s.size()+1,vector<unsigned long long int>(t.size()+1,0));for(int i=0;i<=s.size();i++){dp[i][0]=1;}for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];else dp[i][j]=dp[i-1][j];}}return dp[s.size()][t.size()];}
};583. 两个字符串的删除操作
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();j++){if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}int len=dp[word1.size()][word2.size()];int res=word1.size()-len+(word2.size()-len);return res;}
};第二种方法：
class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j] 使word1的前i-1个字符和word2的前j-1个字符相同所需要的最小步数//dp[i][j]=dp[i-1][j-1]或者 dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2)//dp[i][0]初始化为i，dp[0][j]初始化为jvector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));for(int i=0;i<=word1.size();i++){dp[i][0]=i;}for(int j=1;j<=word2.size();j++){dp[0][j]=j;}for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();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,dp[i][j-1]+1);}}return dp[word1.size()][word2.size()];}
};72. 编辑距离
class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j] word1字符串0~i-1转换成word2字符串0~j-1所使用的最少操作数//dp[i][j]=dp[i-1][j-1]或者 dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)//dp[i][0]初始化为i dp[0][j]初始化为jvector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));for(int i=0;i<=word1.size();i++){dp[i][0]=i;}for(int j=0;j<=word2.size();j++){dp[0][j]=j;}for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();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[word1.size()][word2.size()];}
};647. 回文子串
class Solution {
public:int countSubstrings(string s) {//dp[i][j]从i到j子串是否为回文子串 true,false//s[i]!=s[j]或者s[i]==s[j](i==j true或者i+1==j true或者i+1<j if(dp[i+1][j-1]==true)dp[i][j]=true else dp[i][j]=false)//全部初始化为false //从下往上，从左往右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=0;j<s.size();j++){if(s[i]==s[j]){if(i==j||i+1==j) {dp[i][j]=true;res++;}else if(i+1<j){if(dp[i+1][j-1]==true){dp[i][j]=true;res++;}}}}}return res;}
};方法二：（双指针法）
class Solution {
public:int doubleKey(int i,int j,int n,const string& s){int res=0;while(i>=0&&j<n&&s[i]==s[j]){i--;j++;res++;}return res;}int countSubstrings(string s) {int count=0;for(int i=0;i<s.size();i++){count+=doubleKey(i,i,s.size(),s);//以一个为中心点count+=doubleKey(i,i+1,s.size(),s);//以两个为中心点}return count;}
};516. 最长回文子序列
class Solution {
public:int longestPalindromeSubseq(string s) {//dp[i][j] 下标从i到j的子序列中最长的回文子序列的长度为dp[i][j]//s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2;s[i]!=s[j]时，dp[i][j]=max(dp[i+1][j],dp[i][j-1])//先全部初始化为0，dp[i][i]初始化为1。因为这个递推公式遍历不到单个字符的回文子序列//从下到上，从左往右vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));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]);}}return dp[0][s.size()-1];}
};动规end!