最难啃的骨头开始啃了

斐波拉契数组变形系列

70.爬楼梯

在这里插入图片描述
dp方程:

dp[i] = dp[i-1] + dp[i-2]

自底向上迭代

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

自顶向下记忆化递归:

class Solution {
    private int[] cache;

    public int climbStairs(int n) {
        if (n == 0) return 1;
        cache = new int[n + 1];
        cache[0] = 1;
        return helper(n);
    }

    private int helper(int n) {
        if (n < 3) {
            if (cache[n] == 0) {
                cache[n] = n;
            }
        }
        if (cache[n] == 0) {
            cache[n] = helper(n - 1) + helper(n - 2);
        }
        return cache[n];
    }
}

322.零钱兑换

在这里插入图片描述
思路类似于爬楼梯和斐波拉契数列
f(n)问题可以转换为求f(n-coin[i])的最小值+1的问题

自顶向下,带缓存的递归

class Solution {
   static int cache[];

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        cache = new int[amount + 1];
        return helper(coins, amount);

    }

    private int helper(int[] coins, int amount) {

        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (cache[amount] == 0) {
            int curmin = Integer.MAX_VALUE;
            for (int i = 0; i < coins.length; i++) {
                int res = helper(coins, amount - coins[i]);
                if (res >= 0 && curmin > res)
                    curmin = res+1;
            }
            cache[amount] = (curmin == Integer.MAX_VALUE) ? -1 : curmin;
        }
        return cache[amount];
    }

}

自底向上,dp迭代
因为求最小值,所以先初始化为比最大还大,如果迭代完了小于等于最大值,那么就找到了,如果依然大于最大值,说明没找到

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) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

不同路径系列

62.不同路径

在这里插入图片描述
子问题:右侧点的路径数+下侧点的路径数
得到dp方程:dp[i][j] = dp[i+1][j]+dp[i][j+1]
我们求的是(0,0)点的可能到达的路径数,所以从最后开始遍历,推出(0,0)的总路径数
最后一行和最后一列比较固定,按这个走法只能有一条路能到达,全部初始化为1

class Solution {
     //dp方程
    //opt[i][j] = opt[i+1][j]+opt[i][j+1]
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];

        for (int k = 0; k < m; k++) {
            dp[k][n - 1] = 1;
        }
        for (int k = 0; k < n; k++) {
            dp[m - 1][k] = 1;
        }
        for (int k = m - 2; k >= 0; k--) {
            for (int l = n - 2; l >= 0; l--) {
                dp[k][l] = dp[k+1][l]+dp[k][l+1];
            }
        }
        return dp[0][0];
    }
}

优化:将dp数组简化成一维的
每次迭代只需要暂存最后一排的就够了,暂存数组多开一维,保证最后一列没有初始化也可以使用

class Solution {
     public int uniquePaths(int m, int n) {
        //定义一维的暂存空间就够了,从最后一排开始存储
        int dp[] = new int[n + 1];
        //初始化最后一排,数组大小为n-1,最后一个保持为0,避免迭代时数组越界
        for (int k = 0; k < n; k++) {
            dp[k] = 1;
        }
        for (int k = m - 2; k >= 0; k--) {
            for (int l = n - 1; l >= 0; l--) {
                dp[l] = dp[l]+dp[l+1];
            }
        }
        return dp[0];
    }
}

63.不同路径II

在这里插入图片描述
相比上一个题,增加了障碍物
首先还是初始化dp数组的最后一行和最后一列,然后最后往前递推,遇到障碍物就跳过
初始化发生变化,不再是全赋1,而是从最后一个开始推:如果遇到障碍物就跳过没如果没有障碍物当前值就等于后一个值,一旦遇到了障碍物跳过了,障碍物位置为0,之前的都为0
遍历时,如果遇到障碍物就跳过,障碍物位置就为0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int dp[][] = new int[m][n];
        if (obstacleGrid[m - 1][n - 1] == 0) dp[m - 1][n - 1] = 1;
        //从最后一个点开始,如果不是石头就和前一个一样,如果是石头就初始化为0
        for (int k = m - 2; k >= 0; k--) {
            if (obstacleGrid[k][n - 1] == 0) dp[k][n - 1] = dp[k + 1][n - 1];
        }
        for (int k = n - 2; k >= 0; k--) {
            if (obstacleGrid[m - 1][k] == 0) dp[m - 1][k] = dp[m - 1][k + 1];
        }

        for (int k = m - 2; k >= 0; k--) {
            for (int l = n - 2; l >= 0; l--) {
                if (obstacleGrid[k][l] == 0) dp[k][l] = dp[k + 1][l] + dp[k][l + 1];
            }
        }
        return dp[0][0];
    }
}

优化:将dp数组简化为一维的

思路和上方一致,有一点需要小心,使用二维时如果遇到障碍物可以直接跳过,因为初始化为0,而使用一维时不行,必须对障碍物进行处理,将障碍物出手动置为1

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int dp[] = new int[n + 1];
        if (obstacleGrid[m - 1][n - 1] == 0) dp[n - 1] = 1;

        for (int k = n - 2; k >= 0; k--) {
            if (obstacleGrid[m - 1][k] == 0) dp[k] = dp[k + 1];
        }

        for (int k = m - 2; k >= 0; k--) {
            for (int l = n - 1; l >= 0; l--) {
                if (obstacleGrid[k][l] == 0) dp[l] = dp[l] + dp[l + 1];
                else dp[l] = 0;
            }
        }
        return dp[0];
    }
}

120.三角形最小路径和

在这里插入图片描述
和不同路径类似,只是只跑了一半的图,如果不求最小路径而是求路径条数就和不同路径基本一致了

将集合格式改变一下就比较清楚了

  [2],
  [3,4],
  [6,5,7],
  [4,1,8,3]

从倒数第二层开始,找到下一层下面的数和右斜下的数中的小的一个,加上当前位置,就是局部最小了
dp方程:dp[j] = Math.min(dp[j], dp[j + 1]) + num[i][j]

dp初始化为最后一行的下一行,是一个空白行
然后依次向上迭代,最后只剩下第一行第一个就是最小路径的值

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int dp[] = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

不开辟新数组,复用原集合

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {

        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                triangle.get(i).set(j, Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j));
            }
        }
        return triangle.get(0).get(0);
    }
}

自顶向下记忆化递归

class Solution {
    Integer[][] cache;

    public int minimumTotal(List<List<Integer>> triangle) {
        cache = new Integer[triangle.size()][triangle.size()];
        return helper(0, 0, triangle);
    }

    private int helper(int level, int c, List<List<Integer>> triangle) {
        if (cache[level][c] != null) {
            return cache[level][c];
        }
        if (level == triangle.size() - 1) {
            return cache[level][c] = triangle.get(level).get(c);
        }
        int left = helper(level + 1, c, triangle);
        int right = helper(level + 1, c + 1, triangle);
        return cache[level][c] = Math.min(left, right) + triangle.get(level).get(c);
    }
}

64.最小路径和

在这里插入图片描述
二维的dp

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int dp[][] = new int[m][n];
        dp[0][0] = grid[0][0];
        //初始化dp的第一行和第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] += grid[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}

压缩dp数组到一维
dp[0]设置成Integer.MAX_VALUE;从dp[1]开始使用

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int dp[] = new int[n + 1];
        dp[0] = Integer.MAX_VALUE;
        dp[1] = grid[0][0];
        //初始化dp的第一行和第一列
        for (int i = 1; i < n; i++) {
            dp[i + 1] += grid[0][i] + dp[i];
        }
        for (int i = 1; i < m; i++) {

            for (int j = 0; j < n; j++) {
                dp[j + 1] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
            }

        }
        return dp[n];
    }
}

子序列系列

53.最大子序和(子序列最大和)

在这里插入图片描述
dp方程:dp[i] += dp[i-1]
如果前一个值大于零,说明加上它当前值会增大,就加上,如果小于等于零,就不加
每一个位置都求一下最大和,遍历完成获得全局最大和

class Solution {
     public int maxSubArray(int[] nums) {
        int resMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > 0) nums[i] += nums[i - 1];
            resMax = Math.max(resMax, nums[i]);
        }
        return resMax;
    }
}

152.乘积最大子数组(子序列最大积)

在这里插入图片描述
维护两个变量,当前最大值和当前最小值, 如果当前值为负数,就交换最小值和最大值

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE;
        int curmax = 1;
        int curmin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int tmp = curmax;
                curmax = curmin;
                curmin = tmp;
            }
            curmax = Math.max(nums[i], curmax * nums[i]);
            curmin = Math.min(nums[i], curmin * nums[i]);
            max = Math.max(max, curmax);
        }
        return max;
    }
}

解法二:两次遍历
将数组按0分成n个子数组,求不含0的子数组的最大积
正序和逆序分别遍历一次,两个全局最大积的较大值就是最大积

class Solution {
    public int maxProduct(int[] nums) {
        int max = 1;
        int resmax = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            max *= nums[i];
            resmax = Math.max(resmax, max);
            if (max == 0) max = 1;
        }
        max = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            max *= nums[i];
            resmax = Math.max(resmax, max);
            if (max == 0) max = 1;
        }
        return resmax;
    }
}

1143.最长公共子序列(子序列最大公共序列)

在这里插入图片描述
将一维变成二维操作
在这里插入图片描述
自顶向下:从最后开始看,如果最后两个字符一样的,结果等于各自减去最后一个后的长度+1,如果最后两个字符不相同,等于任选一个减去最后一个字符后的计算长度中大的那一个
自底向上:从第一个字符开始,数组从1下标开始,如果两个字符相同,则长度等于各自减一的后计算长度+1,如果不相同,则任选一个减去最后一个字符后的计算长度中大的那一个。自底向上迭代,最后位置就是最终答案

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null) return 0;
        int m = text1.length();
        int n = text2.length();
        int dp[][] = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

打家劫舍系列

198.打家劫舍

在这里插入图片描述
新加一个维度,偷还是不偷
子问题:

  • 如果这一家偷,那么收入等于前一家不偷+这一家偷的 dp[i][1] = nums[i] + dp[i - 1][0];
  • 如果这一家不偷,那么收入等于前一家偷或者不偷的较大值dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[][] dp = new int[n][2];

        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = nums[i] + dp[i - 1][0];
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}

不加维度,问题转换为求dp[i-2]+num[i]和dp[i-1]的较大值的问题
dp方程转换为:dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int dp[] = new int[nums.length];
        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]);
        }
        return dp[nums.length - 1];
    }
}

为了避免判断长度为0 1 2,采用length+2长度的dp数组

class Solution {
    public int rob(int[] nums) {
        int dp[] = new int[nums.length + 2];
        for (int i = 0; i < nums.length; i++) {
            dp[i + 2] = Math.max(dp[i + 1], dp[i] + nums[i]);
        }
        return dp[nums.length + 1];
    }
}

213.打家劫舍II

在这里插入图片描述
与打家劫舍I相比变成了环了,意味着还要考虑如果偷了第一家最后一家不能偷,如果偷了最后一家第一家不能偷

那么问题可以简化成:从第一家到倒数第二家遍历一次从第二家到最后一家遍历一次。这样就破除了环了,然后取较大值返回

在第一个题的基础上进行改造:

一维:

class Solution {
    public int rob(int[] nums) {

        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int dp[] = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length - 1; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        dp[0] = dp[nums.length-2];//暂存第一个遍历结果
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return Math.max(dp[nums.length - 1], dp[0]);
    }
}

简化:

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int dp[] = new int[nums.length + 2];

        for (int i = 0; i < nums.length - 1; i++) {
            dp[i + 2] = Math.max(dp[i + 1], dp[i] + nums[i]);
        }
        int res1 = dp[nums.length];//暂存第一个遍历结果
        Arrays.fill(dp, 0);
        for (int i = 1; i < nums.length; i++) {
            dp[i + 2] = Math.max(dp[i + 1], dp[i] + nums[i]);
        }
        return Math.max(dp[nums.length + 1], res1);
    }
}

二维:

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int dp[][] = new int[nums.length][2];

        dp[0][0] = 0;
        dp[0][1] = nums[0];

        for (int i = 1; i < nums.length - 1; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = nums[i] + dp[i - 1][0];
        }
        int res1 = Math.max(dp[nums.length - 2][0], dp[nums.length - 2][1]);

        dp[1][0] = 0;
        dp[1][1] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = nums[i] + dp[i - 1][0];
        }
        int res2 = Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);

        return Math.max(res1, res2);
    }
}

337.打家劫舍III

在这里插入图片描述
自顶向下傻递归

class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        //当前层和下下层的和
        int val1 = root.val;
        if (root.left!=null)val1+=rob(root.left.left)+rob(root.left.right);
        if (root.right!=null)val1+=rob(root.right.left)+rob(root.right.right);
        //下一层的和
        int val2  = rob(root.left)+rob(root.right);
        return Math.max(val1,val2);
    }
}

自顶向下带缓存的递归

class Solution {
    Map<TreeNode, Integer> cache;

    public int rob(TreeNode root) {
        cache = new HashMap<TreeNode, Integer>();
        return helper(root);
    }

    private int helper(TreeNode root) {
        if (root == null) return 0;
        if (cache.containsKey(root)) return cache.get(root);
        //当前层和下下层的和
        int val1 = root.val;
        if (root.left != null) val1 += helper(root.left.left) + helper(root.left.right);
        if (root.right != null) val1 += helper(root.right.left) + helper(root.right.right);
        //下一层的和
        int val2 = helper(root.left) + helper(root.right);
        cache.put(root, Math.max(val1, val2));
        return cache.get(root);
    }
}

自底向上后序遍历加升维
和前面两个打家劫舍一样,可以升一个维度,用偷或者不偷来描述一次操作
采用后序遍历保证自底向上逐层搜索

class Solution {
    public int rob(TreeNode root) {
        int[] helper = helper(root);
        return Math.max(helper[0], helper[1]);
    }

    //返回结果是偷或者不偷的值
    private int[] helper(TreeNode root) {
        if (root == null) return new int[]{0, 0};

        int[] left = helper(root.left);
        int[] right = helper(root.right);
        //选择偷当前节点,值为当前节点+下一层不偷
        int choose = root.val + left[1] + right[1];
        //选择不偷当前节点,值为下一层偷的最大值的和
        int noChoose = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{choose, noChoose};
    }
}

买卖股票系列

121.买卖股票的最佳时机

在这里插入图片描述
动态规划:
因为最多交易一次,状态一共只有三种

  • 一次都不交易
  • 买了一次
  • 买了一次 卖了一次
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int dp[][] = new int[prices.length][3];

        dp[0][0] = 0;//不操作
        dp[0][1] = -prices[0];//买入
        dp[0][2] = Integer.MIN_VALUE;//卖出,不可能存在

        for (int i = 1; i < prices.length; i++) {
            //可能是当前位置操作的,可也能上一次就操作了
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
        }
        return Math.max(0, dp[prices.length - 1][2]);
    }
}

这个题动态规划就比较晦涩,效率不高,最好还是用贪心来

一次遍历,如果小于最小值更新最小值,如果大于最小值假设卖出得收益,更新最大收益

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;

        int min = Integer.MAX_VALUE;
        int resMax = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                resMax = Math.max(resMax, prices[i] - min);
            }
        }
        return resMax;
    }
}

122.买卖股票的最佳时机II

在这里插入图片描述
动态规划
因为可以无限次买卖,定义两种状态。持有和卖出

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int dp[][] = new int[prices.length][2];

        dp[0][0] = 0;//不持有
        dp[0][1] = -prices[0];//持有,只能是这次买入的

        for (int i = 1; i < prices.length; i++) {
            //当前不持有,可能上次有这次卖了,可能上次就不持有这次不操作
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            //当前持有,可能上次没有这次买入的,可能上次就持有这次不操作
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        return dp[prices.length - 1][0];
    }
}

这个题动态规划就比较晦涩,效率不高,最好还是用贪心来

一次遍历,如果比前一天价格高就前一天买当天卖

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
}

123.买卖股票的最佳时机III

在这里插入图片描述
因为最多交易两次,状态一共只有五种

  • 一次都不交易
  • 买了一次
  • 买了一次 卖了一次
  • 买了一次 卖了一次 买了一次
  • 买了一次 卖了一次 卖了一次 卖了一次

针对这五种状态进行规划。

class Solution {
     public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;

        //二个维度:第几天,买卖状态
        int dp[][] = new int[prices.length][5];
        /**
         *         j = 0:还未开始交易;
         *         j = 1:第 1 次买入一支股票;
         *         j = 2:第 1 次卖出一支股票;
         *         j = 3:第 2 次买入一支股票;
         *         j = 4:第 2 次卖出一支股票。
         */
        dp[0][0] = 0;
        //第一次买入
        dp[0][1] = -prices[0];
        //第一次买入两个,不可能
        dp[0][3] = Integer.MIN_VALUE;

        for (int i = 1; i < prices.length; i++) {
            //可能是当前位置操作的,可也能上一次就操作了
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
            dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
            dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
        }
        return Math.max(0, Math.max(dp[prices.length - 1][2], dp[prices.length - 1][4]));
    }

}

188.买卖股票的最佳时机IV

在这里插入图片描述
当k是一个变量时,我们简单的使用二维枚举状态就不够用了,所以需要在问题1和问题3的基础上升级到三维
三个维度:

  • 第i天
  • 第j次交易
  • 是否持有股票

如果只是简单的把问题1和问题3的代码拿去升维然后循环弄,会发现超时过不了

再次观察,如果k大于天数的一半,说明最大次数满足无限买卖,问题退化成问题2

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length < 2 || k < 1) return 0;

        //k比prices.length的一半大,说明可以转化为问题2,无限次交易
        if (k > prices.length >> 1) {
            return maxProfit(prices);
        }

        //三个维度:第几天、交易次数、是否持有股票
        int dp[][][] = new int[prices.length][k + 1][2];

        //初始化第一天
        for (int i = 1; i < k + 1; i++) {
            dp[0][i][1] = -prices[0];
        }

        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0]);
                dp[i][j][1] = Math.max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1]);
            }
        }
        return dp[prices.length - 1][k][0];
    }
    //贪心实现无限次交易
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
}

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

在这里插入图片描述
如果没有冻结期,那就是无限买卖问题,类似于问题2,所以在问题2的持有和不持有状态上再加一个冻结期状态

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int dp[][] = new int[prices.length][3];

        //初始化第一天
        dp[0][0] = 0;//不持股
        dp[0][1] = -prices[0];//持股
        dp[0][0] = 0;//冷冻期
        for (int i = 1; i < prices.length; 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], dp[i - 1][2] - prices[i]);
            //今天空窗期,说明昨天不持股
            dp[i][2] = dp[i - 1][0];
        }
        return dp[prices.length - 1][0];
    }
}

714.买卖股票的最佳时机含手续费

在这里插入图片描述
如果没有手续费,那就是无限买卖问题,和问题2一样,加上手续费后,贪心就不行了,要交易的次数尽量少利润尽量多

采用动态规划只需要在每次买入或者卖出时扣一次手续费就可以了
代码和思路同问题2基本一致

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices.length < 2) return 0;
        int dp[][] = new int[prices.length][2];

        //初始化第一天
        dp[0][0] = 0;//不持有
        dp[0][1] = -prices[0] - fee;//持有(一次交易扣一次手续费,所以统一在买入时扣)

        for (int i = 1; i < prices.length; 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], dp[i - 1][0] - prices[i] - fee);
        }
        return dp[prices.length - 1][0];
    }
}

尚未分类

32.最长有效括号

在这里插入图片描述
很容易想到暴力法,O(N*2),对暴力进行剪枝,代码如下:
从第一个开始枚举起始,内存循环枚举结尾
如果左括号+1,如果右括号-1
如果计数器小于1说明除成对括号外出现了右括号前没有左括号,退出这一层遍历
如果计数器值为0,更新最大成对的数目

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        int count = 0;
        for (int i = 0; i < s.length()-1; i++) {
            count = 0;
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(j) == '(') count++;
                else count--;
                if (count < 0) break;
                if (count == 0) max = Math.max(max, j - i + 1);
            }
        }
        return max;
    }
}

暴力的时间和空间复杂度都比较高,采用动态规划进行解决:
方法过于巧妙,好不容易理解透彻记录下
在这里插入图片描述

一次遍历字符串,如果是(就跳过,如果是)就进行操作

  • 如果)的前一个字符是(,刚好组成一对,dp[i-2]+2
    举例:index = 3时,dp[i-2] = 2,index = 2index = 3组成一对,dp[3] = dp[1]+2 = 4

  • 如果)的前一个字符不是(,则查找除掉当前成对的字符后的前一个字符是否是(,如果不是就放弃了,当前置为0.如果是dp[i]的值至少为dp[i-1[+2,如果新匹配的字符的前一个字符(i - dp[i - 1] -2)属于上一个符合的子序列,那么两个子序列就可以合并成一个子序列,长度再加上前面的
    举例:index = 7时,dp[i-1]所属的子序列为index5到index6,除去子序列的前一个是index = 4,满足条件,所以dp[7]至少为dp[i-1]+2,然后判断index = 5的前一个index = 4,发现index = 4这个下标存在,就加上dp[4]的值,得到dp[7] = dp]6]+2+dp[4]

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        int dp[] = new int[s.length()];
        //一次遍历字符串,如果连续成对,更新连续值,如果断了连续,重新开始记录
        for (int i = 1; i < s.length(); i++) {
            //左括号跳过,右括号开始判断
            if (s.charAt(i) == ')') {
                //如果右括号的前一个就是左括号
                if (s.charAt(i - 1) == '(') {
                    dp[i] = 2 + (i >= 2 ? dp[i - 2] : 0);
                    //如果去除掉当前有效段之后前的一个字符为(,说明前后能再组成一对
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    //dp[i]的长度至少等于dp[i-1]+2,如果新插入的那个符号前一位还有符号就加入那个位置的dp值(如果那个位置属于前一个段就加上了前一段的长度,如果是单独的就相当于加0
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1]- 2] : 0);
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}

343.整数拆分

在这里插入图片描述
初始化dp数组为1
dp[i]表示i可以拆分后的最大乘积
dp[i]的值是dp[i]、拆分为两个数乘积最大值,拆分为两个数其中一个数被拆分的最大积乘另一个数的积

class Solution {
    public int integerBreak(int n) {
        int dp[] = new int[n + 1];
        Arrays.fill(dp, 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), dp[i - j] * j));
            }
        }
        return dp[n];
    }
}