动态规划专题复习（二）最值问题

文章目录

• 动态规划专题复习（二）最值问题
• • 何为最值问题？
  • 1.最长回文字串
  • • 暴力
    • 记忆化搜索
    • 动态规划
  • 2.最小路径和
  • • 暴力
    • 记忆化搜索
    • 动态规划
  • 3.打家劫舍一
  • • 暴力
    • 记忆化搜索
    • 动态规划
  • 4.打家劫舍二
  • • 动态规划
  • 5.最大子序和
  • • 暴力
    • 动态规划
  • 6.最大子序积
  • • 动态规划
  • 7.最佳买卖股票时机
  • • 暴力
    • 动态规划
  • 8.最佳买卖股票时机含冷冻期
  • • 动态规划
  • 9.买卖股票的最佳时机 II尽可能多的交易
  • • 暴力
    • 动态规划

动态规划专题复习（二）最值问题

最近在复习算法，为明年的春招做准备，欢迎互关呀，共同学习，进步！

何为最值问题？

最值问题就是给出一个问题的最优解，这种最优解，可以是一个问题能求得的最大最小值，一种最优路径等等。

以下问题均摘取自leetcode

1.最长回文字串

暴力

如果使用暴力递归就是遍历所有字串，在遍历字串过程中，判断字串是否是回文串且记录长度

    /*** 判断是否是回文串* @param str* @return*/public boolean isPalindromic(String str){int len = str.length();for(int i = 0;i < len / 2;i++){if(str.charAt(i) != str.charAt(len - i - 1)){return false;}}return true;}/*** 暴力解法* @param s* @return*/public String longestPalindrome(String s) {if(s.equals("")){return "";}int len = s.length();String result = null;int max = 0;//遍历所有子串for(int i = 0;i < len;i++){for(int j = i + 1; j <= len;j++){String str = s.substring(i,j);//判断是否是回文串if(isPalindromic(str) && str.length() > max){result = s.substring(i,j);//是回文串则记录该子串长度max = Math.max(result.length(),max);}}}return result;}

记忆化搜索

使用暴力递归的时间复杂度很高，遍历子串是O(n^{2)，判断是否是回文串则是O(n)，则时间复杂度总的就是O(N}3)，我们要使用记忆化搜索来降低重复的判断

定义一个记录数组:P(i,j)，i是指向从字符串S开始的下标，j是指向从字符串尾部开始的下标

那么

那么，如果我们想知道 P（i,j）是不是回文串，只需要知道P（i+1，j−1）是不是回文串且第i个字符和第j个字符相同即可判断出P（i,j）是回文串

    public String longestPailndrome(String s){int length = s.length();//相当于dp数组，记录中间结果boolean[][] P = new boolean[length][length];//最大字串String maxPal = "";//遍历所有的长度for (int len = 1; len <= length; len++) { //从字符串起始遍历字串for (int start = 0; start < length; start++) {//字串结束下标 = 起始下标 + 字串长度 - 1int end = start + len - 1;//下标已经越界，结束本次循环if (end >= length) { break;}//P(i,j)=(P(i+1,j−1)&&S[i]==S[j])，长度为 1 和 2 的单独判断下P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); if (P[start][end]) {//subString(begin,end) ===> 不包括endmaxPal = s.substring(start, end + 1);}}}return maxPal;}

动态规划

记忆化搜索是自顶向下的过程，那么，动态规划就是自底向上的过程，是一个逆向过程

    /*** 动态规划* @param s* @return*/public String longestPalindrome1(String s) {int length = s.length();//最长回文字串String result = "";//dp数组boolean[][] dp = new boolean[length][length];//对比记忆化搜索就是逆向遍历的过程//i向着字符串开始处遍历，相当于原来的startfor (int i = length - 1; i >= 0; i--) {//j向着字符串尾部遍历，相当于之前的endfor (int j = i; j < length; j++) {//j - i 代表长度减去 1 ===> 字串长度 = end - start + 1//状态转移方程 ；P(i,j)=(P(i+1,j−1)&&S[i]==S[j])dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);if (dp[i][j] &&  j - i + 1 > result.length()) {result = s.substring(i, j + 1);}}}return result;}

2.最小路径和

暴力

递归树如下

    /*** 暴力解法* @param grid* @return*/public int minPathSum2(int[][] grid) {//从启点开始return minpath(grid,0,0);}private int minpath(int[][] grid, int i, int j) {if (i == grid.length || j == grid[0].length)return Integer.MAX_VALUE;//判断是否到达终点if(i == grid.length-1 && j == grid[0].length - 1)return grid[i][j];return grid[i][j] + Math.min(minpath(grid,i + 1,j),minpath(grid,i,j + 1));}

记忆化搜索

从上文的递归树中可以看到有很多重复的计算，利用记忆化搜索暂存这些计算结果

    /*** 记忆化搜索* @param grid* @return*/public int minPathSum(int[][] grid) {int[][] dp = new int[grid.length+1][grid[0].length+1];//从启点开始return minpath1(grid,0,0,dp);}private int minpath1(int[][] grid, int i, int j,int[][] dp) {if (i == grid.length || j == grid[0].length)return Integer.MAX_VALUE;//判断是否到达终点if(i == grid.length-1 && j == grid[0].length - 1)return grid[i][j];if(dp[i][j] != 0){return dp[i][j];}//暂存计算结果dp[i][j] = grid[i][j] + Math.min(minpath1(grid,i + 1,j,dp),minpath1(grid,i,j + 1,dp));return dp[i][j];}

动态规划

那么动态规划就是一个自底向上的过程

    public int minPathSum1(int[][] grid) {for(int i = 0;i<grid.length;i++){for(int j = 0;j<grid[0].length;j++){//第一列if(i == 0 && j != 0) grid[i][j] += grid[i][j - 1];//第一行if(i != 0 && j == 0) grid[i][j] += grid[i - 1][j];//dp动态转移方程：grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);if(i != 0 && j != 0) grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);}}return grid[grid.length-1][grid[0].length - 1];}

3.打家劫舍一

暴力

    /*** 暴力递归* @param nums* @return*/public int rob1(int[] nums){return tryRob(0,nums);}public int tryRob(int index,int[] nums){if(index >= nums.length){return 0;}int max = 0;for(int i = index;i < nums.length;i++){//max：之前能偷取到的最大金额//tryRob(i + 2)继续偷取下下家房子,然后算出偷上下下家房子后的总金额max = Math.max(max,nums[i] + tryRob(i + 2,nums));}return max;}

记忆化搜索

    /*** 记忆化搜索* @param nums* @return*/public int rob2(int[] nums){int[] dp = new int[nums.length];return tryRob1(0,nums,dp);}public int tryRob1(int index,int[] nums,int[] dp){if(index >= nums.length){return 0;}if(dp[index] != 0){return dp[index];}int max = 0;for(int i = index;i < nums.length;i++){max = Math.max(max,nums[i] + tryRob1(i + 2,nums,dp));}dp[index] = max;return max;}

动态规划

由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值,dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额。

    public int rob(int[] nums) {if(nums.length == 0){return 0;}int[] dp =new int[nums.length + 1];dp[0] = 0;dp[1] = nums[0];for(int i = 2;i <= nums.length;i++){//状态转移方程：dp[i] = max{dp[i-1],dp[i-2]+nums[i-1]}dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);}return dp[nums.length];}

4.打家劫舍二

这道题目和第一道打家劫舍的区别就是这道题房屋是环状的，第一道是线性排列，也就是说在这里，头尾的房子是相邻的，只能二选一，因此，我们可以将这个题目分解为两个第一类的打家劫舍

• 在不偷窃第一个房子的情况下最大金额是 p1；
• 在不偷窃最后一个房子的情况下最大金额是 p2 。
• 取p1，p2最大值

动态规划

    public int rob(int[] nums) {if(nums.length == 0) return 0;if(nums.length == 1) return nums[0];return Math.max(tryRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),tryRob(Arrays.copyOfRange(nums, 1, nums.length)));}public int tryRob(int[] nums) {if(nums.length == 0){return 0;}int[] dp =new int[nums.length + 1];dp[0] = 0;dp[1] = nums[0];for(int i = 2;i <= nums.length;i++){//状态转移方程：dp[i] = max{dp[i-1],dp[i-2]+nums[i-1]}dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);}return dp[nums.length];}

5.最大子序和

暴力

    /*** 暴力穷举* @param nums* @return*/public int maxSubArray1(int[] nums) {int sum;int max = Integer.MIN_VALUE;//穷举所有子序for(int i = 0;i < nums.length;i++){sum = 0;for(int j = i ;j < nums.length;j++){sum += nums[j];if(sum > max){max = sum;}}}return max;}

动态规划

状态转移方程：sum(i) = Max{sum(i - 1) + nums[i] ,nums[i]}

sum(i) —> 代表从0开始的到i的闭区间中，所有连续子数组的和的最大值

    /*** 动态规划* @param nums* @return*/public int maxSubArray2(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];//记录子数组最大和 int max = dp[0];for(int i = 1;i < nums.length;i++){//状态转移方程：sum(i) = Max{sum(i - 1) + nums[i] ,nums[i]}dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);if(dp[i] > max){max = dp[i];}}return max;}

6.最大子序积

动态规划

最大乘积可以由正数正数和负数负数得到，因此，需要同时记录下最大值和最小值。

    public int maxProduct(int[] nums) {if (nums == null || nums.length == 0) {return 0;}//记录结果int result = nums[0];int dpMax = nums[0];int dpMin = nums[0];for (int i = 1; i < nums.length; i++) {int curMax = Math.max(Math.max(dpMax * nums[i], dpMin * nums[i]), nums[i]);int curMin = Math.min(Math.min(dpMax * nums[i], dpMin * nums[i]), nums[i]);result = Math.max(result, curMax);dpMax = curMax;dpMin = curMin;}return result;}

7.最佳买卖股票时机

暴力

    public int maxProfit(int[] prices) {int max = 0;//从第一个元素遍历到倒数第二个元素for(int i = 0;i < prices.length-1;i++){//从第二个元素遍历到最后一个元素,保证买入在卖出前for(int j = i+1;j < prices.length;j++){int profile = prices[j] - prices[i];if(profile > max){max = profile;}}}return max;}

动态规划

    public int maxProfitWithDp1(int[] prices) {if(prices.length == 0){return 0;}//最小买入价int min = prices[0];//最大利润int max = 0;for(int i = 0;i<prices.length;i++){//找出最小买入价min = Math.min(prices[i],min);//找到最大利润max = Math.max(max,prices[i] - min);}return max;}

其实这道题目虽然在leetcode上归类为动态规划，但是我并不觉得这道题目在动态规划思想上有很多的体现

8.最佳买卖股票时机含冷冻期

状态分析

主要有三种状态：

• 持有股票
• 卖出股票
• 冷冻期（什么都不干）

由于存在三种状态，所以时间复杂度可以达到O（3^n）

状态转换图：

推导状态转移方程：

动态规划

    public int maxProfit(int[] prices) {int sold = 0;int rest = 0;int hold = Integer.MIN_VALUE;for(int i : prices){int preSold = sold;//状态转移方程：// newHold = Max{oldHold,rest - price[i]}// newSold = hold + price[i]// newRest = Max{oldRest,oldSold}sold = hold + i;hold = Math.max(hold,rest - i);rest = Math.max(preSold,rest);}return Math.max(sold,rest);}

9.买卖股票的最佳时机 II尽可能多的交易

暴力

    public int maxProfit(int[] prices) {return getMaxProfit(prices,0);}/*** 暴力* @param prices* @param start* @return*/public int getMaxProfit(int prices[], int start){//边界条件if(start >= prices.length){return 0;}//最大利润int max = 0;for(int i = start;i < prices.length;i++){int maxProfit = 0;for(int j = i + 1;j < prices.length;j++){if(prices[i] < prices[j]){//尽可能多的交易,在j卖出后，马上在j（即i + 1）买入，然后就继续寻找下一个卖出点int profit = prices[j] - prices[i] + getMaxProfit(prices,i+1);if(maxProfit < profit){maxProfit = profit;}}}if(max < maxProfit){max = maxProfit;}}return max;}

同一天可以先卖出,再买入(等于这天没有操作),比如 [1, 2, 3],我们可以第一天买入,第二天卖出得 2 - 1, 第二天再买入,第三天卖出得3 - 2,总共2,相当于第二天不用操作也行.受上一题思路,如果存在数组为[a1, a2, a3] ,那么 a3 - a1 = (a2 - a1) + (a3 - a2),所以只看今明两天，只要明天比今天贵，那今天买明天卖就赚到，否则不做操作就是相当于+0，以此类推即可。

    /*** 贪心算法* @param prices* @return*/public int maxProfit1(int[] prices) {int result = 0;for(int i = 1;i < prices.length;i++){result += Math.max(0,prices[i] - prices[i - 1]);}return result;}

动态规划

对于这道题目，我认为python写起来更易懂

状态图：

    def maxProfit(self, prices: List[int]) -> int:if not prices:return 0n = len(prices)dp = [[0]*2 for _ in range(n)]# dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票dp[0][0], dp[0][1] = 0, - prices[0]for i in range(1, n):dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])return dp[n-1][0]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！