动态规划题目练习
动态规划
- 按摩师
- 打家劫舍
- 打家劫舍||
- 删除并获得点数
- 粉刷房子
- 买卖股票的最佳时机含冷冻期
- 买卖股票的最佳时机含手续费
- 买卖股票的最佳时机|||
- 买卖股票的最佳时机IV
按摩师
题目解析：按摩师有很多预约，相邻的预约不可以都选，求最大预约时长
动态规划
1.状态表示：f[i]表示以i位置结尾，i位置选最大预约时长，g[i]表示以i位置结尾，i位置不选最大预约时长
2.状态转移方程：f[i] = g[i-1] + nums[i] g[i] = max(f[i-1],g[i-1])
3.初始化：g[0] = 0 f[0] = nums[0]
4.填表顺序：从左向右
5.返回值：max(f[n-1],g[n-1])
classSolution{publicintmassage(int[]nums){intn=nums.length;//没有一个数if(n==0){return0;}int[]f=newint[n];//当前位置选int[]g=newint[n];//当前位置不选f[0]=nums[0];for(inti=1;i<n;i++){//更新选当前i位置的f表f[i]=g[i-1]+nums[i];//更新不选当前i位置的g表g[i]=Math.max(f[i-1],g[i-1]);}returnMath.max(g[n-1],f[n-1]);}}打家劫舍
题目解析：一个专业的小偷，进行偷窃，如果两个相邻的房屋同时被偷窃，系统会报警，也就是小偷不可以相邻都进行偷窃，其可以偷窃最高总金额，和上题一样相邻不可以都偷
动态规划，依旧使用f和g两个表分别表示i位置结尾，i位置偷 / 不偷的最高总金额
classSolution{publicintrob(int[]nums){intn=nums.length;int[]f=newint[n];int[]g=newint[n];f[0]=nums[0];for(inti=1;i<n;i++){f[i]=g[i-1]+nums[i];g[i]=Math.max(f[i-1],g[i-1]);}returnMath.max(f[n-1],g[n-1]);}}打家劫舍||
题目解析：相邻房屋不可以都进行偷窃，并且首尾是相邻的，求可以偷窃的最高总金额
和上一题唯一区别就是这里 0 和 n-1位置相邻，此时可以分为两种情况求最大值即可
偷nums[0]，nums[1]和nums[n-1]因为相邻都不可以偷，求[2,n-2]相邻不可以偷的最大总金额 + nums[0]
不偷nums[0], nums[1]和nums[n-1]可以偷/不偷，求[1,n-1]相邻不可以偷的最大总金额
动态规划
1.状态表示：f[i]表示偷到nums[i]的最大总金额，g[i]表示偷到不偷nums[i]的最大总金额
2.状态转移方程：f[i] = g[i-1] + nums[i] g[i] = max(f[i-1],g[i-1])
3.初始化：g[0] = 0 f[0] = nums[0]
4.填表顺序：从左向右
5.返回值：max(f[n-1],g[n-1])
classSolution{publicintrob(int[]nums){intn=nums.length;//第一个位置偷 / 不偷//偷nums[0] 1 和 n-1位置不可以偷//不偷nums[0] 1 和 n-1位置任意returnMath.max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));}publicintrob1(int[]nums,intleft,intright){if(left>right){return0;}intn=nums.length;int[]f=newint[n];int[]g=newint[n];f[left]=nums[left];for(inti=left+1;i<=right;i++){f[i]=g[i-1]+nums[i];g[i]=Math.max(f[i-1],g[i-1]);}returnMath.max(f[right],g[right]);}}删除并获得点数
题目解析：不断选nums[i]，可以任意选，但是选过获取到nums[i]点数
以后nums[i] 和 nums[i] -1和nums[i]+1与其值相同都会删除
转化：使用一个arr数组，arr[ nums[i] ] = nums[i]的所有点数，上面会进行删除这里转化成相邻不可以选的问题
1.状态表示：以i位置结尾，f[i]表示选nums[i]的最大点数，g[i]表示不选nums[i]的最大点数
2.状态转移方程：f[i] = g[i-1] + arr[i] g[i] = max(f[i-1],g[i-1])
3.初始化：g[0] = 0 f[0] = nums[0]
4.填表顺序：从左向右
5.返回值：max(f[n-1],g[n-1])
classSolution{publicintdeleteAndEarn(int[]nums){intn=nums.length;intm=0;for(inti=0;i<n;i++){m=Math.max(m,nums[i]);}//将其nums下标对应的值//作为arr的下标，arr[num[i]]的值是nums[i]出现的总和int[]arr=newint[m+1];for(inti=0;i<n;i++){arr[nums[i]]+=nums[i];}//转换成，相邻不可以选问题int[]f=newint[m+1];int[]g=newint[m+1];for(inti=1;i<=m;i++){f[i]=g[i-1]+arr[i];g[i]=Math.max(g[i-1],f[i-1]);}returnMath.max(f[m],g[m]);}}粉刷房子
题目解析：有三种颜色选择，每种颜色涂刷房子对应费用不同，相邻房子不可以涂同一种颜色，求最小花费
1.状态表示：以i位置结尾，dp[i][0]到i位置选红色最小花费，dp[i][1]到i位置选蓝色最小花费，dp[i][0]到i位置选绿色最小花费
2.状态转移方程：
dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0]
dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1]
dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2]
3.初始化：dp[0][0] = costs[0][0] , dp[0][1] = costs[0][1],dp[0][2] = costs[0][2]
4.填表顺序：从左向右，三个表同时
5.返回值：min(dp[n-1][0],dp[n-1][1],dp[n-1][2])
classSolution{publicintminCost(int[][]costs){//1.行下标表示房子，列下标表示涂成对应颜色花费intn=costs.length;int[][]dp=newint[n][3];//列表示选的颜色dp[0][0]=costs[0][0];dp[0][1]=costs[0][1];dp[0][2]=costs[0][2];for(inti=1;i<n;i++){dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i][0];dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+costs[i][1];dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+costs[i][2];}returnMath.min(Math.min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);}}classSolution{publicintminCost(int[][]costs){//1.行下标表示房子，列下标表示涂成对应颜色花费intn=costs.length;int[][]dp=newint[n+1][3];//列表示选的颜色for(inti=1;i<=n;i++){dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];}returnMath.min(Math.min(dp[n][0],dp[n][1]),dp[n][2]);}}买卖股票的最佳时机含冷冻期
题目解析：每天都有股票，可以买入/卖出，手中有股票不可以再进行买入，除非将手中股票卖出，卖出之后有一天冷却期，求出最大利润
1.状态表示：i天结束之后不同状态最大利润，dp[i][0]之后“买入”dp[i][1]之后是“可交易”，dp[i][0]之后是“冷却期”
2.状态转移方程：
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]);
dp[i][2] = dp[i-1][0] + prices[i];
3.初始化：dp[0][0] = prices[0] , dp[0][1] = dp[0][2] = 0
4.填表顺序：从左向右，三个表同时
5.返回值：Math.max(dp[n-1][1],dp[n-1][2])
classSolution{publicintmaxProfit(int[]prices){intn=prices.length;int[][]dp=newint[n][3];//买入//可交易//冷冻期dp[0][0]=-prices[0];//买入for(inti=1;i<n;i++){//买入 i-1天可能买入i天啥也不干 或者 i-1天使可交易状态dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]);//冷冻期，卖出dp[i][2]=dp[i-1][0]+prices[i];}returnMath.max(dp[n-1][1],dp[n-1][2]);}}买卖股票的最佳时机含手续费
题目解析：可以无限次买入和卖出，但手中有股票不可以进行再次买入，除非卖出，每次交易(买入和卖出整个过程)都有手续费
1.状态表示
f[i] : i天结束之后，处于买入状态的最大利润
g[i] : i天结束之后，处于买出状态的最大利润
2.状态转移方程
f[i] = Math.max(f[i-1],g[i-1] - prices[i]);
g[i] = Math.max(g[i-1],f[i-1] + prices[i] - fee);
3.初始化
f[0] = -prices[0] g[0] = 0
4.填表顺序
从左到右
5.返回值
g[n-1]
classSolution{publicintmaxProfit(int[]prices,intfee){intn=prices.length;int[]f=newint[n];//买入状态int[]g=newint[n];//卖出状态f[0]=-prices[0];for(inti=1;i<n;i++){f[i]=Math.max(f[i-1],g[i-1]-prices[i]);g[i]=Math.max(g[i-1],f[i-1]+prices[i]-fee);}returng[n-1];}}买卖股票的最佳时机|||
题目解析：最多可以进行两笔交易(买入和卖出)，但手中有股票不可以进行再次买入，除非卖出
1.状态表示
f[i][j] : i天结束之后，进行了j笔交易 处于买入状态的最大利润
g[i] : i天结束之后，进行了j笔交易处于买出状态的最大利润
2.状态转移方程
f[i][j] = Math.max(f[i-1][j],g[i-1][j] - prices[i]);
g[i][j] = Math.max(g[i-1][j],f[i-1][j-1] + prices[i]);
3.初始化
f[0][0] = -prices[0] g[0][0] = 0 f[0][1] = f[0][2] = -0X3f3f3f3f;
4.填表顺序
从上到下，每行从左到右
5.返回值
g表最后一行中最大值
这里初始化其为-Integer最小值，后续运算可能会出现溢出问题 因此这里使用-0x3f3f3f3f,也就是最小值的一半classSolution{publicintmaxProfit(int[]prices){intn=prices.length;int[][]f=newint[n][3];//列表示完整几笔交易int[][]g=newint[n][3];//初始化第一行intINT=0X3f3f3f3f;for(inti=1;i<3;i++){f[0][i]=g[0][i]=-INT;}f[0][0]=-prices[0];for(inti=1;i<n;i++){for(intj=0;j<3;j++){f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);//未初始化第一列g[i][j]=g[i-1][j];if(j>=1){g[i][j]=Math.max(g[i][j],f[i-1][j-1]+prices[i]);}}}returnMath.max(Math.max(g[n-1][0],g[n-1][1]),g[n-1][2]);}}买卖股票的最佳时机IV
题目解析：上面III是最多进行两笔交易，这里最多进行k笔交易，思路和上面一样，直接将2换成k就行
1.状态表示
f[i][j] : i天结束之后，进行了j笔交易 处于买入状态的最大利润
g[i] : i天结束之后，进行了j笔交易处于买出状态的最大利润
2.状态转移方程
f[i][j] = Math.max(f[i-1][j],g[i-1][j] - prices[i]);
g[i][j] = Math.max(g[i-1][j],f[i-1][j-1] + prices[i]);
3.初始化
f[0][0] = -prices[0] g[0][0] = 0 g表和f表中第一行[0] [1,k] = -0X3f3f3f3f;不影响后面结果
4.填表顺序
从上到下，每行从左到右
5.返回值
g表最后一行中最大值
细节：这里并没有直接初始化为Integer.MIN_VALUE,后面进行运算可能会出现溢出风险 这里总共有 n 天，最多可以进行 n/2笔交易，可以k=min(k,n/2)classSolution{publicintmaxProfit(intk,int[]prices){intn=prices.length;k=Math.min(k,n/2);intINT=0x3f3f3f3f;int[][]f=newint[n][k+1];int[][]g=newint[n][k+1];for(intj=1;j<k;j++){f[0][j]=g[0][j]=-INT;}f[0][0]=-prices[0];for(inti=1;i<n;i++){for(intj=0;j<=k;j++){f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j-1>=0){g[i][j]=Math.max(g[i][j],f[i-1][j-1]+prices[i]);}}}//最后一列最大值intret=0;for(intj=0;j<=k;j++){ret=Math.max(ret,g[n-1][j]);}returnret;}}