本文共 4724 字,大约阅读时间需要 15 分钟。
宅家防疫期间leetcode上小刷了十余道线性动态规划算法题,是时候自己总结提炼一下DP思想了。
我把总结的题目主要分为两类序列匹配类和生活类。 第一类的代表热题:第二类的代表热题:
以下为7道题的思路和代码实现class Solution { public int lengthOfLIS(int[] nums) { if(nums.length==0) return 0; for(int i=1; i1; j--){ if(dp[j] < dp[i]) dp[j] = dp[j-1]+1; } } }}
之所以最先写这道题,因为之前用的是贪心算法,二分搜索比较难想到
public static int lengthOfLIS(int[]nums) { if(nums.length < 2) return nums.length; //LIS数组存放最长子序列的数组,但并非时刻都存放的是最长子序列 int[] LIS = new int[nums.length]; LIS[0] = nums[0];//数组有负整数的情况 int end = 0; for(int i=1; iLIS[end]){ end++; LIS[end]=nums[i]; } //如果当前nums[i]小于子序列最后一位,则用二分法搜索子序列中比nums[i]大的最小数 else{ int left = 0,right =end; while(left = nums[i]; right = pivot; } } LIS[right]=nums[i]; } } return end+1; }
public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { //nums[i] > 0,说明对结果有增益,dp[i]再加当前遍历值 //nums[i] <= 0,说明对结果无增益,dp[i]直接更新为当前遍历数字 dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]); if (max < dp[i]) { //关键步:取每次遍历的当前最大和 max = dp[i]; } } return max; }
class Solution { public int longestCommonSubsequence(String text1, String text2) { int n1 = text1.length(); int n2 = text2.length(); int[][] dp = new int[n1+1][n2+1]; for(int i=0; i
public int minDistance(String word1, String word2) { int n1 = word1.length(); int n2 = word2.length(); int[][] dp = new int[n1+1][n2+1]; for(int i=1; i<=n1; i++) dp[i][0] = dp[i-1][0] +1; for(int j=1; j<=n2; j++) dp[0][j] = dp[0][j-1] +1; for(int i=1; i<=n1; i++){ for(int j=1; j<=n2; j++){ //word1和word2的该位字符相同,不需要改动。 if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; //如果字符不同,则取该步之前的状态基础上做删除,修改,插入中的最小改动 else dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1; } } return dp[n1][n2]; }
股票系列的问题推荐一个总结很到位的思路:
class Solution { public int maxProfit(int[] prices) { int n = prices.length; if(prices.length==0)return 0; int[][] dp = new int[n][2]; //行表示第 i天,列表示是否买入当天股票 dp[0][0] = 0; //i = 0 时 dp[i-1] 是不合法的。 dp[0][1] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = Math.max(dp[i-1][1], -prices[i]); } return dp[n - 1][0]; }}+思路:和上一题的思路基本一致,区别在于交易次数从 1 变成 无限次 那么dp[i][1] 就等于dp[i-1][1]和dp[i-1][0]-prices[i]中更大的结果。因为前 i 天也可以有买入交易了,也就是买股票的第 i天所获利润和第 i-1 直接相关。
class Solution { public int maxProfit(int[] prices) { if(prices.length==0) return 0; int[][] dp = new int[prices.length][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for(int i=1; i
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; // 注意:因为要比较的是最小值,不可能是结果的初始化值就得赋一个最大值 Arrays.fill(dp, amount + 1); dp[0] =0; for(int i=1; i<=amount; i++){ for(int coin: coins){ //如果可包含coin,那么剩余钱是i−coins,要兑换的硬币数是 dp[i−coins]+1 if(coin <= i) dp[i] = Math.min(dp[i],dp[i-coin]+1); } } return dp[amount]<=amount ? dp[amount] : -1; }}
如果这篇文章对你有帮助,请点赞让我知道吧,我会更加努力给大家分享好的内容,谢谢~
转载地址:http://mfrsi.baihongyu.com/