1. 练习题目

  1. https://leetcode-cn.com/problems/unique-paths/
  2. https://leetcode-cn.com/problems/unique-paths-ii/
  3. https://leetcode-cn.com/problems/longest-common-subsequence/
  4. https://www.bilibili.com/video/av53233912?from=search&seid=2847395688604491997
  5. https://leetcode-cn.com/problems/climbing-stairs/description/
  6. https://leetcode-cn.com/problems/triangle/description/
  7. https://leetcode-cn.com/problems/maximum-subarray/
  8. https://leetcode-cn.com/problems/maximum-product-subarray/description/
  9. https://leetcode-cn.com/problems/coin-change/
  10. https://leetcode-cn.com/problems/coin-change-2/
  11. https://leetcode-cn.com/problems/house-robber/
  12. https://leetcode-cn.com/problems/house-robber-ii/description/
  13. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/#/description
  14. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
  15. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
  16. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
  17. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
  18. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
  19. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
  20. https://leetcode-cn.com/problems/perfect-squares/
  21. https://leetcode-cn.com/problems/edit-distance/ （重点）
  22. https://leetcode-cn.com/problems/jump-game/
  23. https://leetcode-cn.com/problems/jump-game-ii/
  24. https://leetcode-cn.com/problems/unique-paths-iii/
  25. https://leetcode-cn.com/problems/longest-valid-parentheses/
  26. https://leetcode-cn.com/problems/minimum-path-sum/
  27. https://leetcode-cn.com/problems/edit-distance/
  28. https://leetcode-cn.com/problems/decode-ways
  29. https://leetcode-cn.com/problems/maximal-square/
  30. https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
  31. https://leetcode-cn.com/problems/frog-jump/
  32. https://leetcode-cn.com/problems/split-array-largest-sum
  33. https://leetcode-cn.com/problems/student-attendance-record-ii/
  34. https://leetcode-cn.com/problems/task-scheduler/
  35. https://leetcode-cn.com/problems/palindromic-substrings/
  36. https://leetcode-cn.com/problems/minimum-window-substring/
  37. https://leetcode-cn.com/problems/burst-balloons/

2. 题解

2.1 不同路径#62（中等）

https://leetcode-cn.com/problems/unique-paths/

class Solution {
    public int uniquePaths(int m, int n) {
        //法一：动态规划。时间复杂度O(m*n),空间复杂度O(m*n)
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
}

2.2 不同路径Ⅱ#63（中等）

https://leetcode-cn.com/problems/unique-paths-ii/

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //法一：动态规划。时间复杂度O(m*n),空间复杂度O(m*n)
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        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++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

2.3 最长公共子序列#1143（中等）

https://leetcode-cn.com/problems/longest-common-subsequence/

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //法一：动态规划。时间复杂度O(m*n),空间复杂度O(m*n)
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char ch1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char ch2 = text2.charAt(j - 1);
                if (ch1 == ch2) {
                    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[m][n];
    }
}

2.4 爬楼梯#70（简单）

https://leetcode-cn.com/problems/climbing-stairs/description/

class Solution {
    public int climbStairs(int n) {
        //法四：动态规划,时间复杂度O(n),空间复杂度O(1)
        int a = 0, b = 0, c = 1;
        for (int i = 0; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }
}

2.5 三角形最小路径和#120（中等）

https://leetcode-cn.com/problems/triangle/description/

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //法一：动态规划，时间复杂度O(n^2),空间复杂度O(n^2)
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
        }
        // 结果是在最后一行，所以要看结果就把最后一行统计，找到最小值即可。
        int minResult = dp[n-1][0];
        for (int i = 1; i < n; i++) {
            minResult = Math.min(minResult, dp[n-1][i]);
        }
        return minResult;
    }
}

2.6 最大子数组和#53（简单）

https://leetcode-cn.com/problems/maximum-subarray/

class Solution {
    public int maxSubArray(int[] nums) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(n)
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }
        int result = dp[0];
        for (int i = 0; i < n; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

2.7 乘积最大子数组#152（中等）

https://leetcode-cn.com/problems/maximum-product-subarray/description/

class Solution {
    public int maxProduct(int[] nums) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(n)
        int n = nums.length;
        int[] minF = new int[n];
        int[] maxF = new int[n];
        System.arraycopy(nums, 0, minF, 0, n);
        System.arraycopy(nums, 0, maxF, 0, n);
        for (int i = 1; i < n; i++) {
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
            maxF[i] = Math.max(minF[i - 1] * nums[i], Math.max(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < n; i++) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
}

2.8 零钱兑换#322（中等）

https://leetcode.com/problems/coin-change/description/

class Solution {
    public int coinChange(int[] coins, int amount) {
        //法一：动态规划。时间复杂度O(S * n),空间复杂度O(S),S为金额，n是面额数
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

2.9 零钱兑换Ⅱ#518（中等）

https://leetcode-cn.com/problems/coin-change-2/

class Solution {
    public int change(int amount, int[] coins) {
        // 法一：动态规划.时间复杂度O(s*n),空间复杂度O(n),s是硬币数，n是面额
        // dp[x]是凑成金额为x的所需硬币组合数.
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

2.10 打家劫舍#198（中等）

https://leetcode-cn.com/problems/house-robber/

class Solution {
    public int rob(int[] nums) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(n)
        int length = nums.length;
        if (length == 1) return nums[0];
        if (length == 2) return Math.max(nums[0], nums[1]);
        //dp[i]是从0到第i家偷取的最高金额
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        //第i晚偷和不偷
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length-1];
    }
}

2.11 打家劫舍Ⅱ#213（中等）

https://leetcode-cn.com/problems/house-robber-ii/description/

class Solution {
    public int rob(int[] nums) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(1)
        int length = nums.length;
        if (length == 1) return nums[0];
        if (length == 2) return Math.max(nums[0], nums[1]);
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        // 这里已经是对空间进行优化过后的代码了，first和second就是之前的dp[i-1]和dp[i-2]
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

2.12 买卖股票的最佳#121（简单）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/#/description

class Solution {
    public int maxProfit(int[] prices) {
        //法一：动态规划.时间复杂度O(n),空间复杂度O(n)
        int length = prices.length;
        if (length < 2) return 0;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            // 0不持股，1持股
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 由于只能买入卖出一次，否则应该是dp[i-1][0]-prices[i];
            dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
        }
        return dp[length-1][0];
    }
}

2.13 买卖股票的最佳时机Ⅱ#122（中等）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

class Solution {
    public int maxProfit(int[] prices) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(n)
        int length = prices.length;
        //dp[i][0]表示第i天不持有股票的收益，dp[i][1]表示第i天持有股票的收益
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < 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]);
        }
        return dp[length-1][0];
    }
}

2.14 买卖股票的最佳时机Ⅲ#123（困难）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

class Solution {
    public int maxProfit(int[] prices) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(1)
        int length = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < length; i++) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}

2.15 股票买卖的最佳时机含冷冻期#309（中等）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

class Solution {
    public int maxProfit(int[] prices) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(n)
        if (prices.length <= 1) {
            return 0;
        }
        int length = prices.length;
        // dp[i][0]表示第i天持有股票，dp[i][1]表示第i天不持有股票，dp[i][2]表示处于冷冻期
        int[][] dp = new int[length][3];
        // 初始条件
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;

        for (int i = 1; i < length; i++) {
            //第i天持有，昨天持有，昨天不处于冷冻期今天买入
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            //第i天不持有，昨天的不处于冷冻期，昨天处于冷冻期
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][2]);
            //第i天处于冷冻期，昨天卖出
            dp[i][2] = dp[i-1][0] + prices[i];
        }
        //最后结果是三者最大值
        return Math.max(dp[length-1][1], dp[length-1][2]);
    }
}

2.16 买卖股票的最佳时机Ⅳ#188（困难）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/ 这题我选择直接cv答案

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];

        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }

        return Arrays.stream(sell[n - 1]).max().getAsInt();
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iv-by-8xtkp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.17 买卖股票的最佳时机含手续费#714（中等）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

class Solution {
    public int maxProfit(int[] prices, int fee) {
        //法一：动态规划。时间复杂度O(n),空间复杂度O(n)
        if (prices.length <= 1) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[length-1][0];
    }
}