动态规划
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]=0
vector<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，其他初始化为0
vector<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]初始化为j
vector<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]初始化为j
vector<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!