简单多状态dp问题

1.按摩师面试题 17.16. 按摩师 - 力扣LeetCode1.题目解析一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。2.算法原理1.状态表示根据经验题目要求f[i]表示:选择到i位置的时候,选择nums[i],此时最长预约时长g[i]表示:选择到i位置的时候,不选择nums[i],此时最长预约时长2.状态转移方程f[i] g[i-1]nums[i]g[i] max{f[i-1],g[i-1])3.初始化f[0]nums[0]g[0]04.填表顺序从左到右,两个表都要填5.返回值max(f[n-1],g[n-1])3.代码实现class Solution { public int massage(int[] nums) { int n nums.length; int[] f new int[n]; int[] g new int[n]; if(n0){ return 0; } f[0] nums[0]; for(int i 1;in;i){ f[i] g[i-1] nums[i]; g[i] Math.max(f[i-1],g[i-1]); } return Math.max(f[n-1],g[n-1]); } }2.打家劫舍213. 打家劫舍 II - 力扣LeetCode1.题目解析你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都都围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统,如果两间相邻的房子在同一时间被小偷闯入,系统会自动报警给定一个代表每个房屋存放金额的非负整数数组计算你在不触发警报装置的情况下 今晚能够偷窃到的最高金额。2.算法原理这道题和打家劫舍一的不同是首位是相连的3.代码实现class Solution { public int rob(int[] nums) { int n nums.length; return Math.max(myRob(nums,1,n-1),nums[0]myRob(nums,2,n-2)); } public int myRob(int[] nums,int left,int right){ if(leftright){ return 0; } int n nums.length; int[] f new int[n]; int[] g new int[n]; f[left] nums[left]; for(int i left1;iright;i){ f[i] g[i-1] nums[i]; g[i] Math.max(f[i-1],g[i-1]); } return Math.max(f[right],g[right]); } }3.删除并获得点数740. 删除并获得点数 - 力扣LeetCode1.题目解析给你一个整数数组nums你可以对它进行一些操作。每次操作中选择任意一个nums[i]删除它并获得nums[i]的点数。之后你必须删除所有等于nums[i] - 1和nums[i] 1的元素。开始你拥有0个点数。返回你能通过这些操作获得的最大点数2.算法原理arr[i]表示i这个数出现的总和问题就转换成在arr中进行打家劫舍3.代码实现class Solution { public int deleteAndEarn(int[] nums) { int mx0; for(int x:nums){ mxMath.max(x,mx); } int[] arrnew int[mx1]; for(int x:nums){ arr[x]x; } int[] fnew int[mx1]; int[] gnew int[mx1]; f[0]arr[0]; for(int i1;imx;i){ f[i]g[i-1]arr[i]; g[i]Math.max(f[i-1],g[i-1]); } return Math.max(f[mx],g[mx]); } }4.粉刷房子LCR 091. 粉刷房子 - 力扣LeetCode1.题目解析假如有一排房子共n个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。例如costs[0][0]表示第 0 号房子粉刷成红色的成本花费costs[1][2]表示第 1 号房子粉刷成绿色的花费以此类推。请计算出粉刷完所有房子最少的花费成本。2.算法原理1.状态表示根据经验题目要求dp[i][0]表示刷到i位置最后一个位置刷红色,此时的最小花费dp[i][1]表示刷到i位置最后一个位置刷蓝色,此时的最小花费dp[i][2]表示刷到i位置最后一个位置刷绿色,此时的最小花费2.状态转移方程dp[i][0] min(dp[i-1][1],dp[i-1][2])cost[i][0];dp[i][1] min(dp[i-1][0],dp[i-1][2])cost[i][1];dp[i][2] min(dp[i-1][1],dp[i-1][0]) cost[i][2];3.初始化4.填表顺序从左到右,从上到下5.返回值min(dp[n-1][0],dp[n-1][1],dp[n-1][2])3.代码实现class Solution { public int minCost(int[][] costs) { int n costs.length; int[][] dp new int[n][3]; dp[0][0] costs[0][0]; dp[0][1] costs[0][1]; dp[0][2] costs[0][2]; for(int i 1;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][1],dp[i-1][0]) costs[i][2]; } return Math.min(Math.min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]); } }5.买卖股票的最佳时机含冷冻期309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCode1.题目解析给定一个整数数组prices其中第prices[i]表示第i天的股票价格 。​设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。注意:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。2.算法原理1.状态表示根据经验题目要求dp[i][0] 买入dp[i][1] 可交易dp[i][2] 冷冻期2.状态转移方程dp[i][0]max(dp[i-1][0],dp[i-1][1]-price[i])dp[i][1]max(dp[i-1][1],dp[i-1][2])dp[i][2]dp[i-1][0]price[i]3.初始化dp[0][0]-p[0]dp[0][1]0;dp[0][2]0;4.填表顺序从左到右5.返回值返回max(dp[n-1][0],dp[n-1][1],dp[n-1][2])3.代码实现class Solution { public int maxProfit(int[] p) { int n p.length; int[][] dp new int[n][3]; dp[0][0] -p[0]; for(int i 1;in;i){ dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]-p[i]); dp[i][1] Math.max(dp[i-1][1],dp[i-1][2]); dp[i][2] dp[i-1][0] p[i]; } return Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]); } }6.买卖股票的最佳时机含手续费714. 买卖股票的最佳时机含手续费 - 力扣LeetCode1.题目解析给定一个整数数组prices其中prices[i]表示第i天的股票价格 整数fee代表了交易股票的手续费用。你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。2.算法原理1.状态表示根据经验题目要求dp[i]表示第i天结束之后,能获得的最大利润dp[i][0]表示第i天买入dp[i][1]表示第i天卖出3.代码实现class Solution { public int maxProfit(int[] prices, int fee) { int nprices.length; int[] fnew int[n]; int[] gnew int[n]; f[0]-prices[0]; g[0]0; for(int i1;in;i){ f[i]Math.max(g[i-1]-prices[i],f[i-1]); g[i]Math.max(f[i-1]prices[i]-fee,g[i-1]); } return Math.max(f[n-1],g[n-1]); } }7.买卖股票的最佳时机123. 买卖股票的最佳时机 III - 力扣LeetCode1.题目解析给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。2.算法原理1.状态表示根据经验题目要求f[i][j]表示在第i天结束之后,完成了j次交易,此时出入买入状态的最大利润g[i][j]表示在第i天结束之后,完成了j次交易,此时处于卖出状态的最大利润2.状态转移方程f[i][j]max(f[i-1][j],g[i-1][j]-p[i])g[i][j]max(g[i-1][j],f[i-1][j-1]p[i])3.初始化第0行从第一个位置开始负无穷(更好的做法是最小值选-0x3f3f3f3f,这样不会越界)4.填表顺序从上往下,从左到右5.返回值g表中最后一行的最大值3.代码实现class Solution { public int maxProfit(int[] p) { int np.length; int[][] fnew int[n][3]; int[][] gnew int[n][3]; int min0x3f3f3f3f; for(int i0;i3;i){ f[0][i]-min; g[0][i]-min; } f[0][0]-p[0]; g[0][0]0; for(int i1;in;i){ for(int j0;j3;j){ f[i][j]Math.max(f[i-1][j],g[i-1][j]-p[i]); g[i][j]g[i-1][j]; if(j-10){ g[i][j]Math.max(g[i][j],f[i-1][j-1]p[i]); } } } int ret0; for(int j0;j3;j){ retMath.max(ret,g[n-1][j]); } return ret; } }