前言 动态规划也是重点啊，所以多找点题目写写，基本都是啥卡的
有的太简单的弱智题目就不放这了哈
有障碍了
区别就是在递推公式要加上判断条件，以及如果障碍在第一行或者第一列的时候，初始化的问题
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; //如果在起点或终点出现了障碍，直接返回0 if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) { return 0; } for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) { dp[i][0] = 1; } for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) { dp[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0; } } return dp[m - 1][n - 1]; } }
一开始尝试找规律没找到
思路
背包问题 01背包问题dp[i][j]是什么：0-i的物品放大哦容量为j的背包的最大价值
二维数组：**dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);**
换成一维就是： dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
一维01背包必须先遍历物品
然后遍历背包时是倒序便利
套路：
//先遍历物品，再倒序遍历背包 for(int i=0;i<weight.length;i++) { for(int j=sumweight;j>=weight[i];j--) { dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i]); } }
有时候weight和value是同一个数组
而完全背包问题，如果是纯完全背包问题，无所谓遍历顺序
如果是装满背包有多少种方法，要分是排列数还是组合数：组合数：先物品，排列数：先背包
完全背包问题套路：
// 先遍历物品，再遍历背包 for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量，因为是无限取，所以可以正序遍历 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } //先背包，再物品 for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 for(int i = 0; i < weight.size(); i++) { // 遍历物品 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }
就是给你物品列表，价值就是具体的数，然后容量也没确定，反正就是看你能不能使价值等于所有数加起来的/2
0-1背包问题，因为每个数只能用一次
卡尔的思路是重量就等于价值，这样的好处是什么，就是背包的容量是可以被确定的
class Solution { public boolean canPartition(int[] nums) { int values=0; for(int i=0;i<nums.length;i++) { values+=nums[i]; } if(values%2!=0)return false; values/=2;//目标价值 int []dp=new int[values+1];//背包最大就是和价值相同 for(int i=0;i<nums.length;i++) { for(int j=values;j>=nums[i];j--) { dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]); } } return dp[values]==values; } }
这道题目等价于什么：把数组分为两部分，让两部分的差尽可能相等或者小，那么不就和上一题一样么
public int lastStoneWeightII(int[] stones) { int sum=0; for(int i:stones) { sum+=i; } int target=sum/2; int[]dp=new int[1501]; for(int i=0;i<stones.length;i++) { for(int j=target;j>=stones[i];j--) { dp[j]=Math.max(dp[j], dp[j-stones[i]]+stones[i]); } } return sum-2*dp[target]; }
思路：转化为背包问题，分为+集合和-集合，最后结果就是sum=＋集合加上-集合
target=＋集合减去-集合
然后得出，＋集合要等于（tartget+sum）/2
这种装满背包有多少种方法的递推公式：dp[j]+=dp[j-numbers[i]]，dp[j]为装满容量为j的背包有多少种方法
public int findTargetSumWays(int[] nums, int target) { int sum=0; for(int num:nums) { sum+=num; } if((sum+target)%2!=0)return 0; if(target<0&&sum<-target)return 0; int left=(sum+target)/2; int[]dp=new int[left+1]; dp[0]=1;//根据题目推导的 for(int i=0;i<nums.length;i++) { for(int j=left;j>=nums[i];j--) { dp[j]+=dp[j-nums[i]]; } } return dp[left]; }
这就到了完全背包问题
有了目标和的基础，做这个不难
//这里面coins就是物品，然后价值和重量也是相等的，就是coins的数值，然后总容量就是amount //dp[j]:容量为j有多少种凑法 //地推：dp[j]+=dp[j-weight[i]] public int change(int amount, int[] coins) { int []dp=new int[amount+1]; dp[0]=1;//当容量为0只有一种，那就是什么也不装 for(int i=0;i<coins.length;i++) { for(int j=coins[i];j<=amount;j++) { dp[j]+=dp[j-coins[i]]; } } return dp[amount]; }
零钱兑换2是问有多少种凑法，这个是问题最少硬币个数
硬币是无线的，那么也是一个完全背包问题
看我一开始写的：
//dp[j]为容量为j的背包，装满他的最少硬币个数 //这题目也是一样，重量等于价值，就是coins【i】 //递推公式：dp[j],dp[j-coins[i]]推出，但是还得保证dp[j-conis[i]]的可以凑成的 //初始化：dp[0]=0; public int coinChange(int[] coins, int amount) { int[]dp=new int[amount+1]; for(int i=0;i<coins.length;i++) { for(int j=coins[i];j<=amount;j++) { if(dp[j-coins[i]]!=0) { dp[j]=dp[j-coins[i]]+1; } } } return dp[amount]; }
我漏了哪些思考：应该取最小的dp[j]，因为双循环你的dp[j]肯定会比较不止一次啊
所以修改：
//dp[j]为容量为j的背包，装满他的最少硬币个数 //这题目也是一样，重量等于价值，就是coins【i】 //递推公式：dp[j],dp[j-coins[i]]推出，但是还得保证dp[j-conis[i]]的可以凑成的 //初始化：dp[0]=0; public int coinChange(int[] coins, int amount) { int[]dp=new int[amount+1]; for(int i=0;i<dp.length;i++) { dp[i]=Integer.MAX_VALUE;//初始化成最大值，防止被覆盖 } dp[0]=0; for(int i=0;i<coins.length;i++) { for(int j=coins[i];j<=amount;j++) { if(dp[j-coins[i]]!=Integer.MAX_VALUE) { dp[j]=Math.min(dp[j-coins[i]]+1,dp[j]); } } } return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];//还等于最大值说明凑不出来 }
这个一眼完全背包问题啊
public int numSquares(int n) { int max=Integer.MAX_VALUE; int[]dp=new int[n+1]; Arrays.fill(dp, max); dp[0]=0; for(int i=1;i*i<=n;i++) { for(int j=i*i;j<=n;j++) { dp[j]=Math.min(dp[j], dp[j-i*i]+1);//一定能凑成，所以不需要判断了 } } return dp[n]; }
可以重复使用，一眼完全背包啊吗，因为这里其实是排列数，就是你的字符得有顺序，所以先遍历背包
//也是背包问题背包就就是给的String s， //物品列表就是wordDICT //然后可以重复使用，说明是完全背包问题 //但是单词有顺序，是排列数，所以是先遍历背包 public boolean wordBreak(String s, List<String> wordDict) { boolean []dp=new boolean[s.length()+1];//dp[i]:长度为i能否背凑成 dp[0]=true; for(int i=0;i<=s.length();i++) { for(int j =0;j<i&&!dp[i];j++)//遍历物品，注意，这里是遍历字符串并且判断他是不是物品 { if(dp[j]&&wordDict.contains(s.substring(j,i))) { dp[i]=true; } } } return dp[s.length()]; }
打家劫舍和股票问题 //每个房间都有两个选择：偷和不偷 //dp[i]:走到这个房间能偷到的最高金额 //偷：dp[i]=dp[i-2]+nums[i] //不偷：dp[i]=dp[i-1] public int rob(int[] nums) { int []dp=new int[nums.length]; dp[0]=nums[0]; if(nums.length==1)return dp[0]; dp[1]=Math.max(nums[0], nums[1]); for(int i=2;i<nums.length;i++) { dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]); } int res=Integer.MIN_VALUE; return dp[nums.length-1]; }
比上一题多了一个条件,首尾相邻
其实就是把打家劫舍抽象了
class Solution { //区别就是和上一题相比，这一题最后一个和第一个是相邻的，那么我们直接分两种情况，第一件偷和第一间不偷 public int rob(int[] nums) { if(nums.length==0)return 0; if(nums.length==1)return nums[0]; int v1=solve(nums, 0, nums.length-2);//偷第一件，那最后一件不能投 int v2=solve(nums, 1, nums.length-1);//不偷异地检 return v1>v2?v1:v2; } public int solve(int[] nums,int l,int r) { if(l==r)return nums[l]; int []dp=new int[nums.length]; dp[l]=nums[l]; dp[l+1]=Math.max(nums[l], nums[l+1]); for(int i=l+2;i<=r;i++) { dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]); } return dp[r]; } }
有一说一这题是算在贪心算法里
//维护当前的最小值，和当前的最大利润，计算本次利润和最大利润比较即可 public int maxProfit(int[] prices) { int []res=new int[prices.length]; int minvalue=Integer.MAX_VALUE; int maxprofit=Integer.MIN_VALUE; for(int i=0;i<prices.length;i++) { res[i]=prices[i]-minvalue>0?prices[i]-minvalue:0; minvalue=Math.min(prices[i], minvalue); maxprofit=Math.max(res[i], maxprofit); } return maxprofit; }
但是为了后面的不能用贪心算法解的题目呢，还是得会动态规划怎么写
那么这就涉及到二维dp了dp[i][0]表示第i天持有股票,dp[i][1]表示第i天不持有股票
public int maxProfit(int[] prices) { int[][]dp=new int[prices.length][2]; dp[0][0]=-prices[0];//第一天持有，那么直接减去数值 dp[0][1]=0; for(int i=1;i<prices.length;i++) { dp[i][0]=Math.max(dp[i-1][0], -prices[i]);//持有，那么要么是今天买，要么是之前买的 dp[i][1]=Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);//不持有，要么是卖了，要么是没买 } return dp[prices.length-1][1];//你最后肯定得卖掉 }
比上一题多了的部分就是可以多次购买出售了
但是这题用动态规划理解太复杂了，我们直接上贪心算法：只要今天股价比昨天高，就交易
public int maxProfit(int[] prices) { int len=prices.length; if(len<2) return 0; int res=0; for(int i=1;i<len;i++) { int diff=prices[i]-prices[i-1]; if(diff>0) { res+=diff; } } return res; }
因为你不限制交易次数啊，所以我们可以把所有的利润空间全部拿下
这题你就不能用贪心了，只能老老实实动态规划了，草!!!!
多维动态规划的关键在于：拆分状态
这里就能拆成四个状态：
第一次持有，第一次不持有，第二次持有，第二次不持有
分别对应dp[i][1][2][3][4]
那么递推公式呢
dp[i][1]第一次持有，所以要么是今天买了，-prices[i]，要么是之前买过了dp[i-1][1] dp[i][2]第一次不持有，要么是今天卖了，dp[i-1][1]+price[i]，要么是啥也没干，dp[i-1][2] dp[i][3]第二次持有，要么是今天买了dp[i-1][2]-prices[i]，要么啥也没干dp[i-1][3] dp[i][4]第二次不持有，要么是今天卖了dp[i-1][3]+prives[i]，要么啥也没干，dp[i-1][4]
总结之后易得：
public int maxProfit(int[] prices) { int len=prices.length; int[][]dp=new int[len][5]; dp[0][1]=-prices[0]; dp[0][3]=-prices[0];//初始化 for(int i=1;i<prices.length;i++) { dp[i][1]=Math.max(dp[i-1][1],-prices[i]); dp[i][2]=Math.max(dp[i-1][1]+prices[i],dp[i-1][2]); dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]); dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]); } return dp[len-1][4]; }
至多k次交易，其实根据上一题找规律就行了
买卖两次我们定义是4个状态，5的数组，那么k次就是2k个状态，2k+1大的数组呗
public int maxProfit(int k, int[] prices) { if(prices.length==0)return 0; int len=prices.length; int[][]dp=new int[len][2*k+1]; for(int i=1;i<k*2;i+=2) { dp[0][i]=-prices[0];//初始化，奇数(第i次持有)全部初始化成-prices[0] } for(int i=1;i<len;i++)//找规律一个一个填吧 { for(int j=0;j<k*2-1;j+=2)//对每一天，去计算k个状态，j始终为偶数 { dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);//j+1为奇数，那就是持有 dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);//不持有 } } return dp[len-1][k*2]; }
序列问题 class Solution { //重点是什么，你要和你前面的所有子序列比 public int lengthOfLIS(int[] nums) { int []dp=new int[nums.length]; Arrays.fill(dp, 1); for(int i=1;i<nums.length;i++) { for(int j=0;j<i;j++) { if(nums[i]>nums[j]) { dp[i]=Math.max(dp[j]+1,dp[i]); } } } int res=0; for(int i=0;i<nums.length;i++) { res=Math.max(res, dp[i]); } return res; } }
//要连续了，那就是只用和前面一个比就行了 public int findLengthOfLCIS(int[] nums) { int[]dp=new int[nums.length]; Arrays.fill(dp, 1); for(int i=1;i<nums.length;i++) { if(nums[i]>nums[i-1]) { dp[i]=dp[i-1]+1; }else { dp[i]=1; } } int res=0; for(int i=0;i<dp.length;i++) { res=Math.max(res, dp[i]); } return res; }
//dp[i][j]表示i-1,j-1为结尾的，两个的最长重复子数组 //地推公式：如果相等，那么等于dp[i-1][j-1]+1，因为是子数组，所以无需其他情况 public int findLength(int[] nums1, int[] nums2) { int [][]dp=new int[nums1.length+1][nums2.length+1]; int res=0; for(int i=1;i<=nums1.length;i++) { for(int j=1;j<=nums2.length;j++) { if(nums1[i-1]==nums2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; } res=Math.max(res,dp[i][j]); } } return res; }
你看是不是就是上一题把子数组换成子序列
这种问题统统表示为i-1.j-1为结尾的，这样就不用初始化了
public int longestCommonSubsequence(String text1, String text2) { int len1=text1.length(); int len2=text2.length(); int [][]dp=new int[len1+1][len2+1]; for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(text1.charAt(i-1)==text2.charAt(j-1)) { dp[i][j]=dp[i-1][j-1]+1; }else { dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[len1][len2]; }
//子数组，那就是连续的序列 // public int maxSubArray(int[] nums) { int[]dp=new int[nums.length]; dp[0]=nums[0]; if(nums.length==1) { return dp[0]; } int res=dp[0]; for(int i=1;i<nums.length;i++) { dp[i]=Math.max(dp[i-1]+nums[i], nums[i]); res=Math.max(res, dp[i]); } return res; }
动态规划核心：分割状态
我们的思路是只对一个进行删除修改操作，不做添加,因为对一个加相当于对另一个减
//dp[i][j]为i-1，j-1转换的最少操作次数 //那我们就是删除修改 //删除：可以对1也可以对2 ，修改对谁都是一样的 //所以 是三种状态 //删除1：那么就变成了dp[i-1][j]+1,删除2：dp[i][j-1]+1,修改:dp[i-1][j-1]+1 //那就行了，一股闹比较谁最小就行了 public int minDistance(String word1, String word2) { int m=word1.length(); int n=word2.length(); int[] []dp=new int[m+1][n+1]; for(int i=1;i<=m;i++) { dp[i][0]=i; } for(int j=1;j<=n;j++) { dp[0][j]=j; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(word1.charAt(i-1)==word2.charAt(j-1)) { dp[i][j]=dp[i-1][j-1];//相等就和之前一样啊 }else { dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j], dp[i-1][j-1]))+1; } } } return dp[m][n]; }
有一说一现在写已经很熟了，进步肉眼可见