LeetCode分类刷题----动态规划

509.斐波那契数列

思路：
用一个数组把每个数字都存起来即可。

 public int fib(int n) {if(n==0) {return 0;}if(n==1) {return 1;}int []dp=new int[n];dp[0]=1;dp[1]=1;for(int i=2;i<n;i++) {dp[i]=dp[i-1]+dp[i-2];}return dp[n-1];}

70.爬楼梯

思路：
也是用递推的方法斐波那契数列。

 public int climbStairs(int n) {int []dp=new int[n+1];if(n==1) {return 1;}if(n==2) {return 2;}dp[1]=1;dp[2]=2;for(int i=3;i<n+1;i++) {dp[i]=dp[i-1]+dp[i-2];}return dp[n];}

746.使用最小花费怕楼梯

思路：
当前台阶 的最小花费体力是上一层的最小体力，加上跳出上一层需要花费的体力。或者上两层的最小体力加上跳出上两层需要花费的最小体力。这两个取一个最小值。因为题目要求可以从第0阶开始跳，也可以从第1阶开始跳，所以第0阶和第1阶的初始值为0.

public int minCostClimbingStairs(int[] cost) {int dp[]=new int[cost.length+1];dp[0]=0;dp[1]=0;for(int i=2;i<=cost.length;i++) {dp[i]=Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}return dp[cost.length];}

62.不同路径

思路：
首先确定dp[i][j]的含义。
代表从头到达这个点有多少条路径。
然后递推公式dp[i][j]=dp[i-1][j]+dp[i][j-1]。
初始化首先初始化第一行和第一列，方法都是1。
然后调用递推公式即可。

  public int uniquePaths(int m, int n) {int dp[][]=new int[m][n];//代表要达到这个位置需要多少路径//初始化for(int i=0;i<m;i++) {dp[i][0]=1;}for(int i=0;i<n;i++) {dp[0][i]=1;}for(int i=1;i<m;i++) {for(int j=1;j<n;j++) {dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];

63.不同路径||

思路：
当遇到没有障碍的时候再初始化，如果遇到障碍，后边的就不用初始化了。
然后递推公式中如果不遇到障碍再递推，如果遇到障碍直接初始化为0即可。

public int uniquePathsWithObstacles(int[][] obstacleGrid) {//初始化。如果遇到有障碍直接停下int m=obstacleGrid.length;int n=obstacleGrid[0].length;int dp[][]=new int[m][n];//如果遇到初始位置和终止位置有障碍，直接返回0，因为此路就不通了。if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) {return 0;}//进行初始化，当没障碍的时候才进行初始化for(int i=0;i<m&&obstacleGrid[i][0]==0;i++) {dp[i][0]=1;}for(int i=0;i<n&&obstacleGrid[0][i]==0;i++) {dp[0][i]=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];}

343.整数拆分

思路：
dp[i]数组的含义就是i能拆分到的数值的最大值。
所以从3开始迭代。每个数字再进行拆分。
从1开始。看j*(i-j)。j*(dp[i-j]),dp[i]哪个大。dp[i-j]后边就相当于很多数字相乘。

  public int integerBreak(int n) {if(n==1) {return 0;}if(n==2) {return 1;}int dp[]=new int[n+1];//代表数字i拆分的最大值.//初始化dp[0]=0;dp[1]=0;dp[2]=1;for(int i=3;i<=n;i++) {for(int j=1;j<i;j++) {dp[i]=Math.max(dp[i], Math.max(j*(i-j),j* dp[i-j]));}}return dp[n];}

96.不同的二叉搜索树

思路：
大的节点都是由小的节点推出来的。让1到i分别做根节点，然后生成树的种类是左子树的种类乘以右子树的种类。

 public int numTrees(int n) {int dp[]=new int[n+1];//代表n个节点组成的有多少个情况//初始化dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++) {for(int j=1;j<=i;j++) {//j代表j作为根节点的情况，那么左子树有j-1个节点，右子树有i-j个节点dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}

01背包问题

416.分割等和子集

思路：
转换成背包问题，就是当这个背包装的容量最大时能不能满足target的目标值。

先遍历物品再遍历背包。遍历背包的时候要从后往前遍历，因为下一层的时候可能要用到左上角的值。注意dp数组的含义

public boolean canPartition(int[] nums) {//判断有没有满足平分的数组if(nums==null||nums.length==0) {return false;}int sum=0;for(int num:nums) {sum+=num;}if(sum%2==1) {return false;//如果是奇数的话，肯定是不能平分的}int target=sum/2;int []dp=new int[target+1];//dp数组代表当前容量所能装的最大值for(int i=0;i<nums.length;i++) {//先遍历物品，再遍历背包for(int j=target;j>=nums[i];j--) {dp[j]=Math.max(dp[j], dp[j-nums[i]]+nums[i]);}}return dp[target]==target;}

1049.最后一块石头的重量||

思路：
将石头尽量分成大小相等的两堆，然后分配一个sum/2的容量的背包去装石头这样遍历完整个数组后，背包里装的是尽可能多的石头。装完了之后让剩下的一堆石头减去这堆石头就是剩余的最小的石头了。

  public int lastStoneWeightII(int[] stones) {if(stones==null||stones.length==0) {return 0;}int sum=0;for(int stone:stones) {sum+=stone;}int target=sum/2;int []dp=new int [target+1];//dp数组代表当前容量所能装的最大值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-dp[target]-dp[target];//将石头分成两堆，用大的一堆减去小的一堆} 

494.目标和

思路：
将整个数组分成正数和负数两部分。

  public int findTargetSumWays(int[] nums, int target) {//将数组分成两堆，左边是正数，右边是负数,则有左+右=sum，左-右=target  然后我们就可以求出左边的数 左=(sum+target)/2//左边的数是正数，给一个这样大小的背包，我们去求有多少种这样的方法可以装满这个背包，就是有多少种这样组合的正数可以放在左边//dp[j]的含义。装满j容量大小的背包有dp[j]种方法int sum=0;for(int num:nums) {sum+=num;}//如果target过大 sum将无法满足if ( target < 0 && sum < -target) return 0;if ((target + sum) % 2 != 0) return 0;int temp=(sum+target)/2;int[] dp=new int[temp+1];//递推公式，dp[5]=dp[4]+dp[3]+dp[2]+dp[1]+dp[0]  因为有1的话，还有dp[4]种方法，以此类推就可以了dp[0]=1;for(int i=0;i<nums.length;i++) {//先遍历物品for(int j=temp;j>=nums[i];j--) {dp[j]+=dp[j-nums[i]];}}return dp[temp];}

474.一和零

思路：
这道题的背包变成二维的了。
背包容量有m个0和n个1.
需要统计出每个字符串包含的0和1的个数。然后再去迭代。

public int findMaxForm(String[] strs, int m, int n) {int dp[][]=new int[m+1][n+1];//dp代表当前背包的容量能最多能放多少个含x个0，y个1的元素。m+1，n+1代表二维数组的容量int zeronum;int onenum;for(String str:strs) {zeronum=0;onenum=0;for(char c:str.toCharArray()) {if(c=='0') {zeronum++;}else if(c=='1') {onenum++;}}for(int i=m;i>=zeronum;i--) {for(int j=n;j>=onenum;j--) {dp[i][j]=Math.max(dp[i-zeronum][j-onenum]+1,dp[i][j] );}}}return  dp[m][n];}

完全背包问题

518.零钱兑换||

思路：
已经给了你背包容量的大小，这里只不过是一个物品可以被装很多次，背包从小到大遍历就行了。前提是容量得等于当前硬币的大小。

  public int change(int amount, int[] coins) {//递推表达式int[] dp = new int[amount + 1];//初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装dp[0] = 1;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];}

377.组合总和IV

思路：
这道题要强调元素的顺序。所以先遍历背包，再遍历物品。然后如果背包容量大于等于物品的话，就把它加进去。

 public int combinationSum4(int[] nums, int target) {//因为这个组合强调遍历顺序了，所以不同顺序的物品也要算作不同的结果int dp[]=new int[target+1];//初始化dp[0]=1dp[0]=1;for(int i=0;i<=target;i++) {//先遍历背包for(int j=0;j<nums.length;j++) {if(i>=nums[j]) {//如果dp[i]+=dp[i-nums[j]];}}}return dp[target];}

322.零钱兑换

思路：
要保证最小的数组，把数组初始化成最大值，然后每次去迭代dp[j]都去选取最小的值。
dp[j]的含义。装满容量为j的背包最小的元素要多少。

 public int coinChange(int[] coins, int amount) {int dp[]=new int[amount+1];//初始化dp数组为最大的值for(int i=0;i<amount+1;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++) {//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要if(dp[j-coins[i]]!=Integer.MAX_VALUE) {dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);}}}return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];}

279.完全平方数

思路：
用完全平方数做物品，然后背包容量是目标数大小，然后每次更新最小的数就可以了。

 public int numSquares(int n) {//生成完全平方数做物品int[] dp=new int[n+1];//初始化for(int i=0;i<=n;i++) {dp[i]=Integer.MAX_VALUE;}dp[0]=0;for(int i=1;i*i<=n;i++) {//先遍历物品for(int j=i*i;j<=n;j++) {//再遍历背包if(dp[j-(i*i)]!=Integer.MAX_VALUE) {dp[j]=Math.min(dp[j], dp[j-i*i]+1);}}}return dp[n];}

139.单词拆分

思路：
完全背包问题。将字符串想象成一个背包，每个单词是物品。判断物品能不能装满这个背包即可。因为字符串有顺序问题。所以是排列问题，先遍历背包。再遍历物品。判断j，i之间的字符串在不在物品里边即可。
dp[0]初始化为true，其他初始化为false。

 public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set=new HashSet<>(wordDict);boolean[] valid = new boolean[s.length() + 1];valid[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i && !valid[i]; j++) {if (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}return valid[s.length()];}

打家劫舍

198.打家劫舍

思路：
确定dp数组含义，dp[i]表示从下标i以前所能偷得的最大金币数。
初始化dp[0]和dp[1]。
然后i需要从前两个位置来确定偷还是不偷，这两个状态中去取一个最大值。

 public int rob(int[] nums) {if(nums.length==1) {return nums[0];}int []dp=new int[nums.length];//dp[]数组含义，偷到dp[i]的时候所能偷的最大数量//初始化dp[0]=nums[0];//只能偷一个的话肯定是当前的最大值dp[1]=Math.max(nums[0], nums[1]);//偷两个元素的话是偷前两个元素的最大值for(int i=2;i<nums.length;i++) {dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);//当前的结果是偷i的结果还是不偷i的结果}return dp[nums.length-1];}

213.打家劫舍||

思路：
这道题就是在打家劫舍的基础上判断有没有环，可以分两种情况来考虑，第一种情况就是考虑第一个元素，第二种情况就是考虑最后一个元素。然后这两种情况取一个最大值。

 public int rob(int[] nums) {if (nums == null || nums.length == 0)return 0;int len = nums.length;if (len == 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int x = 0, y = 0, z = 0;for (int i = start; i < end; i++) {y = z;z = Math.max(y, x + nums[i]);x = y;}return z;}

买卖股票

121.买卖股票的最佳时机

思路：
定义两个状态，一个是持有股票的状态，一个是不持有股票的状态，这两个状态都可以通过前一天推出来。
然后找到不持有股票状态的最大值即可，

  public int maxProfit(int[] prices) {//dp数组含义dp[i][0]表示持有股票的最大金钱，持有股票不代表就是这天买的，也可能是前几天买的//dp[i][1]表示不持有股票的最大金钱，卖出股票不代表就是这天卖的，也可能是前几天卖的int [][]dp=new int[prices.length][2];//dp数组初始化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][1], dp[i][0]+prices[i]);//可能是当天卖的}return dp[prices.length-1][1];}

300.最长递增子序列

思路：
从第二个数字开始遍历，然后里边再套一层循环，从i之前的元素开始。如果当前的字母比前边的数字大。那么就取一个最大值。最后输出数组里边的最大值即可。

 public static int lengthOfLIS(int[] nums) {//dp数组定义dp[i]以i为结尾的最长递增子序列的最大值int []dp=new int[nums.length];//初始化Arrays.fill(dp,1);dp[0]=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[i], dp[j]+1);}}}//从dp数组中再找到一个最大值int result = 0;for(int i=0;i<nums.length;i++) {result=Math.max(result,dp[i] );}return result;}

674.最长连续递增序列

思路：
每一个元素和上一个元素比较，如果满足条件就+1.如果不满足，就初始化为1.

public int findLengthOfLCIS(int[] nums) {//定义dp数组，dp[i]代表以i为结尾的最长连续递增子序列int dp[]=new int[nums.length];//初始化dp[0]=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 result = 0;for(int i=0;i<dp.length;i++) {result=Math.max(result, dp[i]);}return result;}

718.最长重复子数组

思路：
定义dp数组含义
dp[i][j]代表数组1到i-1，数组2到j-1的最长重复子数组。
遍历顺序，先遍历数组1，然后遍历数组2如果nums1[i-1]==nums[j-1]。更新dp数组。
结果返回dp数组的最大值即可。

 public int findLength(int[] nums1, int[] nums2) {//dp数组定义代表dp[i][j]代表数组1到i-1，数组2到i-2的最长重复子数组int dp[][]=new int[nums1.length+1][nums2.length+1];//初始化int result=0;//记录最大的结果for(int i=1;i<nums1.length+1;i++) {for(int j=1;j<nums2.length+1;j++) {if(nums1[i-1]==nums2[j-1]) {dp[i][j]=dp[i-1][j-1]+1;}result=Math.max(result, dp[i][j]);}}return result;}

1143.最长公共子序列

思路：
这道题和前一道的区别是这道题不要求连续了。所以要考虑字符串不相等的情况，不相等的时候可以从上边或者左边推出来。

 public int longestCommonSubsequence(String text1, String text2) {int dp[][]=new int[text1.length()+1][text2.length()+1];//确定dp数组含义//dp[i][j]表示字符串1[0,i-1]字符串2[0,j-1]的最长重复子数组，因为这里不考虑需要字符连续的情况。所以需要考虑不相同的qingk for(int i=1;i<=text1.length();i++) {for(int j=1;j<=text2.length();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[text1.length()][text2.length()];}

1035.不相交的线

思路：
其实就是在求两个数字数组的最长公共子序列。

 public int maxUncrossedLines(int[] nums1, int[] nums2) {int dp[][]=new int[nums1.length+1][nums2.length+1];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;}else {dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[nums1.length][nums2.length];}

53.最大子数组和

思路：
dp[i]是以i结尾的最大数组和。当前这个值由dp[i-1]+nums[i],nums[i]中两个数之间选一个最大的。

   public int maxSubArray(int[] nums) {int dp[]=new int[nums.length];//dp数组含义,以i为结尾的最大子数组和if(nums.length==1) {return nums[0];}int result=Integer.MIN_VALUE;//初始化dp[0]=nums[0];for(int i=1;i<nums.length;i++) {dp[i]=Math.max(nums[i], dp[i-1]+nums[i]);result=Math.max(result, dp[i]);}return result;}

392.判断子序列

思路：
这道题就是求最长公共子序列，求出最长公共子序列的长度，然后再和最短的子串长度进行笔记，然后判断这两个是不是相等即可。

 public boolean isSubsequence(String s, String t) {int dp[][]=new int[s.length()+1][t.length()+1];//确定dp数组的含义，dp[i][j]表示字符串1以i-1为结尾，字符串2以j-1为结尾的最长子序列长度for(int i=1;i<=s.length();i++) {for(int j=1;j<=t.length();j++) {if(s.charAt(i-1)==t.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[s.length()][t.length()]==s.length();}

115.不同的子序列

思路：
记住dp定义。
然后dp可以有两个状态推过来，然后记住下一次操作。当s[i-1]和t[j-1]相等时，可以选择用它还可以选择不用它。

 public int numDistinct(String s, String t) {int dp[][]=new int[s.length()+1][t.length()+1];//确定dp数组的含义,dp[i][j]表示以i-1结尾的字符串中有多少个以j-1结尾的子串//初始化dp[0][0]=1;dp[0][1]=0;dp[1][0]=1;for (int i = 0; i < s.length() + 1; i++) {dp[i][0] = 1;}for(int i=1;i<=s.length();i++) {for(int j=1;j<=t.length();j++) {if(s.charAt(i-1)==t.charAt(j-1)) {//这里分为用i-1的情况和不用i-1的情况，例如bagg,bag.dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}else {dp[i][j]=dp[i-1][j];//不相等的话就往前推一位}}}return dp[s.length()][t.length()];}

583.两个字符串的删除操作

思路：
如果相同，dp数组就按照dp[i-1][j-1]
如果比较的字符串不同，那么dp数组就在删上一个、删下一个、两个都删里边选一个比较小的。

public int minDistance(String word1, String word2) {int dp[][]=new int[word1.length()+1][word2.length()+1];//dp数组含义,dp[i][j]以i-1结尾的word1和j-1结尾的word2要达到相同的长度需要删除几个元素//初始化for(int i=0;i<=word1.length();i++) {dp[i][0]=i;}for(int j=0;j<=word2.length();j++) {dp[0][j]=j;}for(int i=1;i<=word1.length();i++) {for(int j=1;j<=word2.length();j++) {if(word1.charAt(i-1)==word2.charAt(j-1)) {//如果当前两个字母相等的话,删不删都无所谓了dp[i][j]=dp[i-1][j-1];}else {//否则，就要取删i-1，删j-1，还是都删中最小的一个dp[i][j]=Math.min(dp[i-1][j]+1, Math.min(dp[i][j-1]+1, dp[i-1][j-1]+2));}}}return dp[word1.length()][word2.length()];}

72.编辑距离

思路：
dp[][]数组定义
dp数组初始化
根据上一个的状态推出dp[i][j]。要不就删一个，要不就更改一个。

public int minDistance(String word1, String word2) {int dp[][]=new int[word1.length()+1][word2.length()+1];//dp数组含义,dp[i][j]表示以i-1结尾的word1要变成j-1为结尾的word2最少操作的次数//初始化for(int i=0;i<=word1.length();i++) {dp[i][0]=i;}for(int j=0;j<=word2.length();j++) {dp[0][j]=j;}for(int i=1;i<=word1.length();i++) {for(int j=1;j<=word2.length();j++) {if(word1.charAt(i-1)==word2.charAt(j-1)) {//如果当前两个字母相等的话,最小移动次数就是去掉这两个字母的移动次数dp[i][j]=dp[i-1][j-1];}else {//否则，就要取删i-1，删j-1，还是更改一个的最小次数dp[i][j]=Math.min(dp[i-1][j]+1, Math.min(dp[i][j-1]+1, dp[i-1][j-1]+1));}}}return dp[word1.length()][word2.length()];}

647.回文子串

思路：
定义dp数组的含义。
然后当s[i]=s[j]时，分析三种情况。
如果满足回文串的时候，返回三种数量即可。

 public int countSubstrings(String s) {boolean dp[][]=new boolean[s.length()][s.length()];//dp[i][j]含义，表示以i为开头，以j为结尾的子串是不是回文串int result=0;//初始化都初始为false‘//遍历顺序，从左下角到右上角开始遍历for(int i=s.length()-1;i>=0;i--) {for(int j=i;j<s.length();j++) {if(s.charAt(i)==s.charAt(j)) {//如果两个字母相等if(j-i<=1) {//一定是回文串，可能是一个字符串，也可能是两个相同的字符串result++;dp[i][j]=true;}else if(dp[i+1][j-1]) {//如果相差距离大于1，里面的子串是回文串，那么这个也就是回文串了result++;dp[i][j]=true;}}}}return result;}

516.最长回文子序列

思路：
定义dp数组含义，然后dp数组可以从i+1，和j-1推出。
或者只考虑一端的数子，然后取这两个较大的值。
最后取一个较大的结果即可。

  public int longestPalindromeSubseq(String s) {int dp[][]=new int[s.length()+1][s.length()+1];//dp数组含义表示dp[i][j]从i开始到j结束的最长的回文子序列//初始化for(int i=0;i<s.length();i++) {dp[i][i]=1;}//遍历顺序从左下角到右上角遍历for(int i=s.length()-1;i>=0;i--) {for(int j=i+1;j<s.length();j++) {if(s.charAt(i)==s.charAt(j)) {//如果两个字母相等的话，那么这个字符串也是一个回文字符串dp[i][j]=dp[i+1][j-1]+2;}else {//如果不是，取两个之间较大的一个dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][s.length()-1];}