LeetCode之Dynamic Programming题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

---

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

---

文章目录：

---

Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

---

输入用例

1. 递减， [5,4,3,2,1]
2. 递增， [1,2,3,4,5]
3. 有增有减

定义int型变量lowest，存储从prices[0..i]的最小值

$$maxProfit = Math.max(maxProfit, prices[i] - lowest)$$

    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int maxProfit = 0;
        int lowest = Integer.MAX_VALUE;
        for (int v : prices) {
            lowest = Math.min(v, lowest);
            maxProfit = Math.max(maxProfit, v - lowest);
        }
        return maxProfit;
    }

---

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

---

斐波那契数列的典型应用。

• 0级台阶：0
• 1级台阶：1
• 2级台阶：2
• 3级台阶：1+2=3
• 4级台阶：2+3=5
• ……
• n级台阶：f(n-2)+f(n-1)=f(n)

注意

1. 不要使用递归，否则遇到大数时，递归太深，容易溢出，同时效率低
2. 最好的方法是定义三个变量（不用建立数组），循环

    public int climbStairs(int n) {
        if (n < 0) {
            return -1;
        } else if (n <= 2) {
            return n;
        }
        // 定义三个变量，空间复杂度是O(1)
        int step1 = 1;
        int step2 = 2;
        int step3 = 0;
        // 三个变量一直循环
        // climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)
        for (int i = 3; i <= n; i++) {
            step3 = step1 + step2;
            step1 = step2;
            step2 = step3;
        }
        return step3;
    }

---

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

---

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        char[] c = s.toCharArray();
        // 对于台阶，需要前两步的值，所以数组最小是3
        int[] step = new int[Math.max(n + 1, 3)];
        step[0] = 1;
        step[1] = 0;
        // 第一个字符不是0，则第一步初始为1
        if (c[0] != '0') {
            step[1] = 1;
        }
        // step[i] = step[i - 1] + step[i - 2];
        // 只不过加step[i - 2]时，需要对c[i - 2]和c[i - 1]判断，组合是否<=26
        for (int i = 2; i <= n; i++) {
            step[i] = 0;
            if (c[i - 1] != '0') {
                step[i] += step[i - 1];
            }
            if (c[i - 2] != '0') {
                if ((c[i - 2] - '0') * 10 + (c[i - 1] - '0') <= 26) {
                    step[i] += step[i - 2];
                }
            }
        }
        return step[n];
    }

---

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

---

本质：求数组不相邻元素最大和

动态规划（背包问题）：设P[i]表示从0~i个房间抢劫的最大收益。

$$P[i]=\begin{cases}nums[i] + P[i-2]，偷第i个\\P[i-1]，不偷第i个\end{cases}$$

每次迭代只需要P的两个元素，并不需要设数组P。设两个变量为：

take :nums[i] + P[i-2]
nonTake:P[i-1]

    public int rob(int[] nums) {
        int take = 0;
        int nonTake = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            take = nums[i] + nonTake;
            nonTake = max;
            max = Math.max(take, nonTake);
        }
        return max;
    }
    public int rob2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] P = new int[nums.length];
        P[0] = nums[0];
        P[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            P[i] = Math.max(nums[i] + P[i - 2], P[i - 1]);
        }
        return P[nums.length - 1];
    }

---

House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

---

参考：LeetCode 198 House Robber

只是这次变成了一个环，那么只要把数组分成两个：不包括第一个元素、不包括最后一个元素，就可以把环拆掉。取House Robber的最大值。

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(help(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                help(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    public int help(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] P = new int[nums.length];
        P[0] = nums[0];
        P[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            P[i] = Math.max(nums[i] + P[i - 2], P[i - 1]);
        }
        return P[nums.length - 1];
    }

---

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

---

动态规划，设dp[x][y]是当前matrix[x][y]最大的正方形的长。

$$dp[x][y]=1 + min\begin{cases}dp[x-1][y]\\dp[x][y-1]\\dp[x-1][y-1]\end{cases}$$

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int mx = matrix.length;
        int my = matrix[0].length;
        int[][] dp = new int[mx][my];
        int max = 0;
        // 初始化第0行
        for (int i = 0; i < my; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                max = 1;
            }
        }
        // 初始化第0列
        for (int i = 1; i < mx; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                max = 1;
            }
        }
        // dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x-1][y-1]) + 1
        for (int x = 1; x < mx; x++) {
            for (int y = 1; y < my; y++) {
                if (matrix[x][y] == '1') {
                    dp[x][y] = Math.min(Math.min(dp[x - 1][y], dp[x][y - 1]),
                            dp[x - 1][y - 1]) + 1;
                    max = Math.max(max, dp[x][y]);
                }
            }
        }
        return max * max;
    }

---

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

---

参考：LeetCode 053 Maximum Subarray

LeetCode第53题Maximum Subarray是求连续和最大的子数组，本题是求连续乘积最大的子数组。

在解法上是一样的，只是在求和时，是负就舍弃。但是在乘积中，因为负数*负数=正数，所以连续乘积为负数时，并不能舍弃这个数，因为如果数组的元素是负数，它可能成为乘积最大的数。

所以LeetCode第53题Maximum Subarray，只需要定义一个变量，用来记录和；本题要定义两个变量：positive和negative，分别记录当前乘积最大值和最小值。

$$max=Math.max(max,positive)$$

    public int maxProduct(int[] nums) {
        int max = nums[0];
        int positive = nums[0];
        int negative = nums[0];
        for (int i = 1; i < nums.length; i++) {
            positive *= nums[i];
            negative *= nums[i];
            if (positive < negative) {
                int t = positive;
                positive = negative;
                negative = t;
            }
            positive = Math.max(positive, nums[i]);
            negative = Math.min(negative, nums[i]);
            max = Math.max(max, positive);
        }
        return max;
    }

---

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

---

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curSum = Math.max(curSum + nums[i], nums[i]);
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }

---

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

---

LeetCode 063 Unique Paths II 
LeetCode 062 Unique Paths

    public int minPathSum(int[][] grid) {
        if (grid == null || grid[0] == null) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int y = 1; y < n; y++) {
            dp[0][y] = dp[0][y - 1] + grid[0][y];
        }
        for (int x = 1; x < m; x++) {
            dp[x][0] = dp[x - 1][0] + grid[x][0];
        }
        for (int y = 1; y < n; y++) {
            for (int x = 1; x < m; x++) {
                int min = Math.min(dp[x - 1][y], dp[x][y - 1]);
                dp[x][y] = min + grid[x][y];
            }
        }
        return dp[m - 1][n - 1];
    }

---

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

动态规划，求解最优化问题，自底向上。

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 将所有平方数置1
        for (int i = 0; i * i <= n; i++) {
            dp[i * i] = 1;
        }
        for (int a = 1; a <= n; a++) {
            for (int b = 1; a + b * b <= n; b++) {
                // 取较小值，a + b * b也可能是平方数
                dp[a + b * b] = Math.min(dp[a] + 1, dp[a + b * b]);
            }
        }
        return dp[n];
    }

---

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

---

定义一个数组K，自下向上存储结果，当处理到第一行时，K[0]就是结果。

在本题中，数组K分别是：

[7, 6, 10, 3]
[9, 10, 10, 3]
[11, 10, 10, 3]

存储结果的部分是：

[7, 6, 10]
[9, 10]
[11]

分析数字7，是题目输入的第三行的6，与其下面相邻的4和1的组合，取最小值； 
分析数字9，是题目输入的第二行的3，与数组[7, 6, 10]中的7和6的组合，取最小值。

核心代码是：

        for (int i = s.length - 2; i >= 0; i--) {
            List<Integer> list = triangle.get(i);
            for (int j = 0; j <= i; j++) {
                s[j] = list.get(j) + Math.min(s[j], s[j + 1]);
            }
        }

    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        if (size == 0) {
            return 0;
        }
        if (size == 1) {
            return triangle.get(0).get(0);
        }
        int[] s = new int[size];
        int k = 0;
        for (Integer v : triangle.get(size - 1)) {
            s[k++] = v;
        }
        for (int i = s.length - 2; i >= 0; i--) {
            List<Integer> list = triangle.get(i);
            for (int j = 0; j <= i; j++) {
                s[j] = list.get(j) + Math.min(s[j], s[j + 1]);
            }
        }
        return s[0];
    }

---

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

1. The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.
4. Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

    public int nthUglyNumber(int n) {
        int[] nums = new int[n];
        nums[0] = 1;
        int i = 0, j = 0, k = 0, t = 1;
        while (t < n) {
            int min = Math.min(Math.min(nums[i] * 2, nums[j] * 3), nums[k] * 5);
            nums[t++] = min;
            if (nums[i] * 2 == min) {
                i++;
            }
            if (nums[j] * 3 == min) {
                j++;
            }
            if (nums[k] * 5 == min) {
                k++;
            }
        }
        return nums[n - 1];
    }

---

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

  1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

---

1. 以n为根结点的二叉树个数=左子树个数*右子树个数
2. 用数组record[n+1]记录以0~n的情况，自底向上，否则会超时

    public int numTrees(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        // record[0]没有用，所以长度是n+1
        // 使用数组，从下向上保存结果，能够节省时间，否则会超时
        int[] record = new int[n + 1];
        record[0] = 1;
        record[1] = 1; // 1个元素时，情况为1
        record[2] = 2; // 2个元素时，情况为2
        for (int i = 3; i <= n; i++) {
            int tmp = 0;
            for (int k = 0; k < i; k++) {
                // 以n为根结点的二叉树个数=左结点的二叉树个数*右结点的二叉树个数
                // 题目所求要包括所有情况，分别以1~n为根结点
                tmp += (record[k] * record[i - k - 1]);
            }
            // 记录1~i时，BST的个数
            record[i] = tmp;
        }
        return record[n];
    }

---

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

---

    public List<TreeNode> generateTrees(int n) {
        int[] array = new int[n];
        // 建立1~n的数组
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        return generateTrees(array);
    }
    List<TreeNode> generateTrees(int[] array) {
        if (array.length == 0) {
            return new ArrayList<TreeNode>(
                    Collections.<TreeNode> singletonList(null));
        }
        ArrayList<TreeNode> rt = new ArrayList<TreeNode>();
        // 数组的每一个元素（array[i]），分别作为根结点
        for (int i = 0; i < array.length; i++) {
            // array[i]作为根结点，array[i]之前的元素为左结点，array[i]之后的元素为右结点
            for (TreeNode left : generateTrees(Arrays.copyOfRange(array, 0, i))) {
                for (TreeNode right : generateTrees(Arrays.copyOfRange(array,
                        i + 1, array.length))) {
                    TreeNode root = new TreeNode(array[i]);
                    root.left = left;
                    root.right = right;
                    rt.add(root);
                }
            }
        }
        return rt;
    }

---

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

---

构造二维数组dp[m][n]，其中

$$dp[i][j]=\begin{cases}dp[i-1][j]+dp[i][j-1], & \text{i≠1且j≠1}\\1, & \text{i=1或j=1}\end{cases}$$

其中dp[m-1][n-1]就是结果。

    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int y = 1; y < n; y++) {
            dp[0][y] = 1;
        }
        for (int x = 1; x < m; x++) {
            dp[x][0] = 1;
        }
        for (int y = 1; y < n; y++) {
            for (int x = 1; x < m; x++) {
                dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

---

Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

---

参考LeetCode 062 Unique Paths

有障碍物的时候（obstacleGrid[i][j]==1），将对应的dp置0（dp[i][j]=0）。

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid[0] == null) {
            return 0;
        }
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int y = 1; y < n; y++) {
            if (obstacleGrid[0][y] == 0) {
                dp[0][y] = 1;
            } else {
                break;
            }
        }
        for (int x = 1; x < m; x++) {
            if (obstacleGrid[x][0] == 0) {
                dp[x][0] = 1;
            } else {
                break;
            }
        }
        for (int y = 1; y < n; y++) {
            for (int x = 1; x < m; x++) {
                if (obstacleGrid[x][y] == 1) {
                    dp[x][y] = 0;
                } else {
                    dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

---