动态规划题目练习

动态规划按摩师打家劫舍打家劫舍||删除并获得点数粉刷房子买卖股票的最佳时机含冷冻期买卖股票的最佳时机含手续费买卖股票的最佳时机|||买卖股票的最佳时机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){intnnums.length;//没有一个数if(n0){return0;}int[]fnewint[n];//当前位置选int[]gnewint[n];//当前位置不选f[0]nums[0];for(inti1;in;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){intnnums.length;int[]fnewint[n];int[]gnewint[n];f[0]nums[0];for(inti1;in;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){intnnums.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(leftright){return0;}intnnums.length;int[]fnewint[n];int[]gnewint[n];f[left]nums[left];for(intileft1;iright;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){intnnums.length;intm0;for(inti0;in;i){mMath.max(m,nums[i]);}//将其nums下标对应的值//作为arr的下标arr[num[i]]的值是nums[i]出现的总和int[]arrnewint[m1];for(inti0;in;i){arr[nums[i]]nums[i];}//转换成相邻不可以选问题int[]fnewint[m1];int[]gnewint[m1];for(inti1;im;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.行下标表示房子列下标表示涂成对应颜色花费intncosts.length;int[][]dpnewint[n][3];//列表示选的颜色dp[0][0]costs[0][0];dp[0][1]costs[0][1];dp[0][2]costs[0][2];for(inti1;in;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.行下标表示房子列下标表示涂成对应颜色花费intncosts.length;int[][]dpnewint[n1][3];//列表示选的颜色for(inti1;in;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] 04.填表顺序从左向右三个表同时5.返回值Math.max(dp[n-1][1],dp[n-1][2])classSolution{publicintmaxProfit(int[]prices){intnprices.length;int[][]dpnewint[n][3];//买入//可交易//冷冻期dp[0][0]-prices[0];//买入for(inti1;in;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] 04.填表顺序从左到右5.返回值g[n-1]classSolution{publicintmaxProfit(int[]prices,intfee){intnprices.length;int[]fnewint[n];//买入状态int[]gnewint[n];//卖出状态f[0]-prices[0];for(inti1;in;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){intnprices.length;int[][]fnewint[n][3];//列表示完整几笔交易int[][]gnewint[n][3];//初始化第一行intINT0X3f3f3f3f;for(inti1;i3;i){f[0][i]g[0][i]-INT;}f[0][0]-prices[0];for(inti1;in;i){for(intj0;j3;j){f[i][j]Math.max(f[i-1][j],g[i-1][j]-prices[i]);//未初始化第一列g[i][j]g[i-1][j];if(j1){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笔交易可以kmin(k,n/2)classSolution{publicintmaxProfit(intk,int[]prices){intnprices.length;kMath.min(k,n/2);intINT0x3f3f3f3f;int[][]fnewint[n][k1];int[][]gnewint[n][k1];for(intj1;jk;j){f[0][j]g[0][j]-INT;}f[0][0]-prices[0];for(inti1;in;i){for(intj0;jk;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-10){g[i][j]Math.max(g[i][j],f[i-1][j-1]prices[i]);}}}//最后一列最大值intret0;for(intj0;jk;j){retMath.max(ret,g[n-1][j]);}returnret;}}