DP刷题练习（三）

int rob(vector<int>& nums) {int n=nums.size();if(n==0) return 0;if(n==1) return nums[0];int dp[n+1];//考虑下标i(包含)，前i个房间所能偷盗最大金币为dp[i]dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<n;i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}       return dp[n-1];}
//对于当前的房间都有不偷和偷两种状态
//不偷是dp[i]=dp[i-1]
//偷是dp[i]=dp[i-2]+nums[i]

打家劫舍二与一的区别在于，头尾是连成环的，就是说头尾是相邻的，针对头尾，我们有三种情况

①头尾都不偷

②头偷尾不偷

③头不偷尾偷

其实又可以发现我们可以将①包含于②③中，我们考虑0—n-2与1—n-1，并没有说我们一定要偷0，或一定要偷n-1，只是不考虑两者同时出现的情况所以我们只要用俩个dp数组分别考虑0—n-2与1—n-1,取其最大值便是结果，其余都与上题一致

int rob(vector<int>& nums) {int n=nums.size();if(n==0) return 0;else if(n==1) return nums[0];else if(n==2) return max(nums[0],nums[1]);int dp1[n-1],dp2[n-1];//定义两个长度为n-1的数组即可//对于dp1，其考虑，不包涵最后一个元素的情况dp1[0]=nums[0],dp1[1]=max(nums[0],nums[1]);for(int i=2;i<n-1;i++) dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i]);//构建一个nums2数组服务于dp2，dp2考虑不包含第一个元素的情况int nums2[n-1];for(int i=0;i<n-1;i++) nums2[i]=nums[i+1];dp2[0]=nums2[0],dp2[1]=max(nums2[0],nums2[1]);for(int i=2;i<n-1;i++) dp2[i]=max(dp2[i-1],dp2[i-2]+nums2[i]);return max(dp1[n-2],dp2[n-2]);}

树形dp入门

我们设置状态dp【0】为不偷当前节点所能获得的最大值，dp【1】为偷当前节点所能获得的最大值

我们采用后序遍历，从下往上遍历，最后看偷根结点，不偷根结点，所能获得的最大值是什么

//偷当前节点：int val1=cur->val+leftdp[0]+rightdp[0];
//当前节点若偷，则其左右儿子不能偷

//不偷当前节点：int val2=max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1]);
//当前节点若不偷，则其左右各取所获最大价值

vector<int> robtree(TreeNode *cur){if(cur==NULL) return vector<int> {0,0};vector<int> leftdp=robtree(cur->left);vector<int> rightdp=robtree(cur->right);//偷当前节点int val1=cur->val+leftdp[0]+rightdp[0];//不偷当前节点int val2=max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1]);return vector<int> {val2,val1};}int rob(TreeNode* root) {vector<int> result=robtree(root);return max(result[0],result[1]);}

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。

就是你的买卖都只能有一次

dp含义如代码所示

dp[i][0]=max(dp[i-1][0],-prices[i]);
//第i天持有股，你可能是之前一天就持有，或者是今天买入才持有，说到底是找最小的价格买入

 dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);
//第i天不持有股，你可以是前一天就不持有了，也可以是前一天就持有了，但是今天卖出

初始化：

dp[0][0]=-prices[0]; //第0天持股，那你第0天肯定要买入！
dp[0][1]=0;          //第0天不持股

int maxProfit(vector<int>& prices) {int n=prices.size();int dp[n][2];//dp[i][0]表示第i天持有股票的所获得的最大利润//dp[i][1]表示第i天不持有股票所获得的最大利润dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],-prices[i]);dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);}return dp[n-1][1];}

本题与上题的区别是股票可以买卖多次，所以你买入股票时你当前拥有的金额可以不是0，所以在此处持股的最大利润如下

dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);

本题有个坑点就是题目说股票可以同一天买入然后卖出

但是题目说了你最多只能持有一支股票，所以你今天要买入，必然前一天不持股所以是dp【i-1]】【1】-prices【i】

然后今天又卖出所以是dp【i-1]】【1】-prices【i】+prices【i】<==> dp【i-1】【1】

   int maxProfit(vector<int>& prices) {int n=prices.size();int dp[n][2];//dp[i][0]表示第i天持有股票的所获得的最大利润//dp[i][1]表示第i天不持有股票所获得的最大利润dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<n;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[n-1][1];}

int maxProfit(vector<int>& prices) {int n=prices.size();int dp[n][5];//dp[i][0]表示不操作//dp[i][1]表示第一次持有//dp[i][2]表示第一次不持有//dp[i][3]表示第二次持有//dp[i][4]表示第二次不持有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<n;i++){dp[i][1]=max(dp[i-1][1],-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[n-1][4];}

由上一题两次的情况可以推广到k次的情况

    int maxProfit(int k, vector<int>& prices) {int n=prices.size();int dp[n][2*k+1];memset(dp,0,sizeof(dp));for(int i=0;i<=2*k;i++){if(i%2==0) dp[0][i]=0;else dp[0][i]=-prices[0];}for(int i=1;i<n;i++){for(int j=1;j<=2*k;j++){if(j%2==0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);else if(j%2!=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);}}return dp[n-1][2*k];}

由于具有冷冻期所以我们要明确

到底是拿一天卖出了股票所以我们把不持有股票的状态进行了拆分

int maxProfit(vector<int>& prices) {int n=prices.size();int dp[n][4];//dp[i][0]表示第i天持有股票//dp[i][1]表示第i天保持卖出股票状态//dp[i][2]表示第i天卖出股票//dp[i][3]表示第i天是冷冻期dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],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];}return max(dp[n-1][3],max(dp[n-1][2],dp[n-1][1]));}