[关闭]
@Yano 2019-09-20T10:50:30.000000Z 字数 15339 阅读 5740

LeetCode Dynamic Programming 题目汇总 （前500题）

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

10 Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

题目描述

Implement regular expression matching with support for '.' and '*'.

The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".") → true
isMatch("ab", ".") → true
isMatch("aab", "c*a*b") → true

代码

  2. class Solution {
  3.     public boolean isMatch(String s, String p) {
  4.         char[] string = s.toCharArray();
  5.         char[] pattern = p.toCharArray();
  6.         boolean[][] dp = new boolean[string.length + 1][pattern.length + 1];
  7.         dp[0][0] = true;
  8.                 for(int i = 2; i <= pattern.length; i++) {
  9.             if(pattern[i - 1] == '*') dp[0][i] = dp[0][i - 2];
  10.         }
  11.         for (int i = 1; i <= string.length; i++) {
  12.             for (int j = 1; j <= pattern.length; j++) {
  13.                 if (pattern[j - 1] == string[i - 1] || pattern[j - 1] == '.') {
  14.                     dp[i][j] = dp[i - 1][j - 1];
  15.                 } else if(pattern[j - 1] == '*') {
  16.                     if(!dp[i][j - 1] && j >= 2) {
  17.                         dp[i][j] = dp[i][j - 2] || ((string[i - 1] == pattern[j - 2] || pattern[j - 2] == '.') && dp[i - 1][j]);
  18.                     } else if(dp[i][j - 1]) {
  19.                         dp[i][j] = dp[i - 1][j] && (string[i - 1] == pattern[j - 2] || pattern[j - 2] == '.');
  20.                     }
  21.                 }
  22.             }
  23.             //System.out.println(Arrays.deepToString(dp));
  24.         }
  25.         return dp[string.length][pattern.length];
  26.     }
  27. }

44 Wildcard Matching

https://leetcode.com/problems/wildcard-matching/

题目描述

Implement wildcard pattern matching with support for '?' and '*'.

The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "") → true
isMatch("aa", "a") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

代码

  2. class Solution {
  3.     public boolean isMatch(String s, String p) {
  4.         char[] string = s.toCharArray();
  5.         char[] pattern = p.toCharArray();
  6.         boolean[][] dp = new boolean[string.length + 1][pattern.length + 1];
  7.         dp[0][0] = true;
  8.                 for(int i = 1; i <= pattern.length; i++) {
  9.             if(pattern[i - 1] == '*') dp[0][i] = dp[0][i - 1];
  10.         }
  11.         for (int i = 1; i <= string.length; i++) {
  12.             for (int j = 1; j <= pattern.length; j++) {
  13.                 if (pattern[j - 1] == '*') {
  14.                     dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
  15.                 } else if (string[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
  16.                     dp[i][j] = dp[i - 1][j - 1];
  17.                 }
  18.             }
  19.         }
  20.         return dp[string.length][pattern.length];
  21.     }
  22. }

32 Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/

题目描述

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

代码

  2. class Solution {
  3.     public int longestValidParentheses(String s) {
  4.         int ans = 0, start = 0;
  5.         Stack<Integer> stack = new Stack<>();
  6.         for (int i = 0; i < s.length(); i++) {
  7.             if (s.charAt(i) == '(') {
  8.                 stack.push(i);
  9.             } else {
  10.                 if (stack.isEmpty()) {
  11.                     start = i + 1;
  12.                 } else {
  13.                     stack.pop();
  14.                     ans = stack.isEmpty() ? Math.max(ans, i - start + 1) : Math.max(ans, i - stack.peek());
  15.                 }
  16.             }
  17.         }
  18.         return ans;
  19.     }
  20. }

70 Climbing Stairs

https://leetcode.com/problems/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?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output:  2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

代码

  2. class Solution {
  3.     public int climbStairs(int n) {
  4.         if(n <= 2) return n;
  5.         // dp 可以优化为两个数
  6.         int[] dp = new int[n + 1];
  7.         dp[1] = 1;
  8.         dp[2] = 2;
  9.         for(int i = 3; i <= n; i++) {
  10.             dp[i] = dp[i - 1] + dp[i - 2];
  11.         }
  12.         return dp[n];
  13.     }
  14. }

72 Edit Distance

https://leetcode.com/problems/edit-distance/

题目描述

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

代码

  2. class Solution {
  3.     public int minDistance(String w1, String w2) {
  4.         int[][] dp = new int[w1.length() + 1][w2.length() + 1];
  5.         for(int i = 0; i <= w1.length(); i++) {
  6.             dp[i][0] = i;
  7.         }
  8.         for(int i = 0; i <= w2.length(); i++) {
  9.             dp[0][i] = i;
  10.         }
  11.                 for(int i = 1; i <= w1.length(); i++) {
  12.            for(int j = 1; j <= w2.length(); j++) {
  13.                 if(w1.charAt(i - 1) == w2.charAt(j - 1)) {
  14.                     dp[i][j] = dp[i - 1][j - 1];
  15.                 } else {
  16.                     // 分别对应删、增、改
  17.                     dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
  18.                 }
  19.             } 
  20.         }
  21.                 return dp[w1.length()][w2.length()];
  22.     }
  23. }

91 Decode Ways

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int numDecodings(String s) {
  4.         if(s == null || s.length() == 0) return 0;
  5.         int len = s.length();
  6.         int[] dp = new int[len + 1];
  7.         dp[0] = 1;
  8.         if(s.charAt(0) != '0') dp[1] = 1;
  9.                 for(int i = 2; i < len + 1; i ++){
  10.             if(s.charAt(i - 1) != '0')
  11.                 dp[i] += dp[i - 1];
  12.             int val = Integer.valueOf(s.substring(i - 2, i));
  13.             if(val >= 10 && val <= 26)
  14.                 dp[i] += dp[i - 2];
  15.         }
  16.         return dp[len];
  17.     }
  18. }

115 Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

题目描述

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

代码

  2. class Solution {
  3.     public int numDistinct(String S, String T) {
  4.         // array creation
  5.         int[][] dp = new int[T.length()+1][S.length()+1];
  6.         // filling the first row: with 1s
  7.         for(int j=0; j<=S.length(); j++) {
  8.             dp[0][j] = 1;
  9.         }
  10.         // the first column is 0 by default in every other rows but the first, which we need.
  11.         /**
  12.              S = [acdabefbc]
  13.         mem[1] = [0111222222]
  14.         mem[2] = [0000022244]
  15.         **/
  16.         for(int i=0; i<T.length(); i++) {
  17.             for(int j=0; j<S.length(); j++) {
  18.                 if(T.charAt(i) == S.charAt(j)) {
  19.                     dp[i+1][j+1] = dp[i][j] + dp[i+1][j];
  20.                 } else {
  21.                     dp[i+1][j+1] = dp[i+1][j];
  22.                 }
  23.             }
  24.         }
  25.         return dp[T.length()][S.length()];
  26.     }
  27. }

139 Word Break

https://leetcode.com/problems/word-break/

题目描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given

s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

代码

  2. class Solution {
  3.     public boolean wordBreak(String s, List<String> wordDict) {
  4.         if (s == null || s.length() == 0) {
  5.             return false;
  6.         }
  7.         Set<String> set = new HashSet<>(wordDict);
  8.         boolean[] dp = new boolean[s.length() + 1];
  9.         dp[0] = true;
  10.         for (int i = 0; i < s.length(); i++) {
  11.             for (int j = 0; j <= i; j++) {
  12.                 if (dp[j] && set.contains(s.substring(j, i + 1))) {
  13.                     dp[i + 1] = true;
  14.                     break;
  15.                 }
  16.             }
  17.             // System.out.println(Arrays.toString(dp));
  18.         }
  19.         return dp[s.length()];
  20.     }
  21. }

140 Word Break II

https://leetcode.com/problems/word-break-ii/

题目描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

代码

  2. class Solution {
  3.     public List<String> wordBreak(String s, List<String> wordDict) {
  4.         List<String> ans = new ArrayList<>();
  5.         if (s == null || s.length() == 0) {
  6.             return ans;
  7.         }
  8.         Set<String> set = new HashSet<>(wordDict);
  9.         boolean[] dp = new boolean[s.length() + 1];
  10.         dp[0] = true;
  11.         for (int i = 0; i < s.length(); i++) {
  12.             for (int j = 0; j <= i; j++) {
  13.                 if (dp[j] && set.contains(s.substring(j, i + 1))) {
  14.                     dp[i + 1] = true;
  15.                     break;
  16.                 }
  17.             }
  18.         }
  19.         if(dp[s.length()]) {
  20.             robot(s, 0, set, ans, "", dp);
  21.         }
  22.         return ans;
  23.     }
  24.     private void robot(String s, int start, Set<String> set, List<String> ans, String out, boolean[] dp) {
  25.         if (start == s.length()) {
  26.             ans.add(out.substring(0, out.length() - 1));
  27.             return;
  28.         }
  29.         for (int i = start; i < s.length(); i++) {
  30.             String word = s.substring(start, i + 1);
  31.             if (dp[i + 1] && set.contains(word)) {
  32.                 robot(s, i + 1, set, ans, out + word + " ", dp);
  33.             }
  34.         }
  35.     }
  36. }

264 Ugly Number II

https://leetcode.com/problems/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, and n does not exceed 1690.

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

代码

  2. class Solution {
  3.     public int nthUglyNumber(int n) {
  4.         List<Integer> ans = new ArrayList<>();
  5.         ans.add(1);
  6.         int i0 = 0, i1 = 0, i2 = 0;
  7.         while (ans.size() < n) {
  8.             int m0 = 2 * ans.get(i0),m1 = 3 * ans.get(i1),m2 = 5 * ans.get(i2);
  9.             int min = Math.min(m0, Math.min(m1, m2));
  10.             if (min == m0) i0++;
  11.             if (min == m1) i1++;
  12.             if (min == m2) i2++;
  13.             ans.add(min);
  14.         }
  15.         return ans.get(n - 1);
  16.     }
  17. }

279 Perfect Squares

https://leetcode.com/problems/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.

代码

  2. class Solution {
  3.     public int numSquares(int n) {
  4.         List<Integer> ans = new ArrayList<>();
  5.         ans.add(0);
  6.         while (ans.size() <= n) {
  7.             int m = ans.size(), val = Integer.MAX_VALUE;
  8.             for (int i = 1; i * i <= m; i++) {
  9.                 val = Math.min(val, ans.get(m - i * i) + 1);
  10.             }
  11.             ans.add(val);
  12.         }
  13.         return ans.get(n);
  14.     }
  15. }

300 Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

题目描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

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

代码

  2. class Solution {
  3.     public int lengthOfLIS(int[] nums) {
  4.         int n = nums.length;
  5.         int[] dp = new int[n];
  6.         int ans = 0;
  7.         for (int i = 0; i < n; i++) {
  8.             dp[i] = 1;
  9.             for (int j = 0; j < i; j++) {
  10.                 dp[i] = Math.max(dp[i], nums[i] > nums[j] ? dp[j] + 1 : 0);
  11.             }
  12.             ans = Math.max(ans, dp[i]);
  13.         }
  14.         return ans;
  15.     }
  16. }

303 Range Sum Query - Immutable

https://leetcode.com/problems/range-sum-query-immutable/

题目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

代码

  2. class NumArray {
  3.     private int[] nums;
  4.     private int[] sums;
  5.     public NumArray(int[] tmp) {
  6.         this.nums = Arrays.copyOf(tmp, tmp.length);
  7.         sums = new int[nums.length + 1];
  8.         for (int i = 0; i < nums.length; i++) {
  9.             sums[i + 1] += nums[i] + sums[i];
  10.         }
  11.     }
  12.     public int sumRange(int i, int j) {
  13.         if (i < 0 || j > nums.length || i > j) {
  14.             return 0;
  15.         }
  16.         return sums[j + 1] - sums[i];
  17.     }
  18. }
  19. /**
  20.  * Your NumArray object will be instantiated and called as such:
  21.  * NumArray obj = new NumArray(nums);
  22.  * int param_1 = obj.sumRange(i,j);
  23.  */

304 Range Sum Query 2D - Immutable

https://leetcode.com/problems/range-sum-query-2d-immutable/

题目描述

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

代码

  1. public class NumMatrix {
  3.     public long[][] sumMatrix;
  5.     public NumMatrix(int[][] matrix) {
  7.         if (matrix == null || matrix.length == 0) {
  8.             return;
  9.         }
  11.         sumMatrix = new long[matrix.length + 1][matrix[0].length + 1];
  13.         for (int i = 0; i < matrix.length; i++) {
  14.             for (int j = 0; j < matrix[0].length; j++) {
  15.                 sumMatrix[i][j + 1] = sumMatrix[i][j] + matrix[i][j];
  16.             }
  17.         }
  18.     }
  20.     public int sumRegion(int row1, int col1, int row2, int col2) {
  22.         if (sumMatrix == null || row1 < 0 || row2 < 0 || col1 < 0
  23.                 || col2 < 0 || row1 >= sumMatrix.length - 1
  24.                 || row2 >= sumMatrix.length - 1
  25.                 || col1 >= sumMatrix[0].length - 1
  26.                 || col2 >= sumMatrix[0].length - 1 || row1 > row2
  27.                 || col1 > col2) {
  28.             return Integer.MIN_VALUE;
  29.         }
  31.         long rt = 0;
  33.         for (int i = row1; i <= row2; i++) {
  34.             rt += sumMatrix[i][col2 + 1] - sumMatrix[i][col1];
  35.         }
  37.         return (int) rt;
  38.     }
  40. }
  43. // Your NumMatrix object will be instantiated and called as such:
  44. // NumMatrix numMatrix = new NumMatrix(matrix);
  45. // numMatrix.sumRegion(0, 1, 2, 3);
  46. // numMatrix.sumRegion(1, 2, 3, 4);

312 Burst Balloons

https://leetcode.com/problems/burst-balloons/

题目描述

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a
number on it represented by array nums.

You are asked to burst all the balloons. If the you burst
balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left
and right are adjacent indices of i. After the burst, the left and right
then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]


Return 167


nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

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

代码

  1. public class Solution {
  3.     public int robot(int idx, int[] nums, boolean[] v) {
  4.         if(idx >= nums.length) {
  5.             return 0;
  6.         }
  7.         int ans = 0;
  8.         for(int i = 0; i < nums.length; i++) {
  9.             if(!v[i]) {
  10.                 v[i] = true;
  11.                 int left = i - 1 >= 0 ? nums[i - 1] : 1;
  12.                 int right = i + 1 < nums.length ? nums[i + 1] : 1;
  13.                 ans = nums[i] * left * right + robot(idx + 1, nums, v);
  14.                 v[i] = false;
  15.             }
  16.         }
  17.         return ans;
  18.     }
  20.     public int maxCoins(int[] nums) {
  21.         boolean[] v = new boolean[nums.length];
  22.         return robot(0, nums, v);
  23.     }
  24. }

322 Coin Change

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

题目描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:

coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

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

代码

  2. class Solution {
  3.     public int coinChange(int[] coins, int amount) {
  4.         int n = coins.length;
  5.         int[] dp = new int[amount + 1];
  6.         Arrays.fill(dp, amount + 1);
  7.         dp[0] = 0;
  8.         for (int i = 1; i <= amount; i++) {
  9.             for (int j = 0; j < n; j++) {
  10.                 if (i >= coins[j]) {
  11.                     dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
  12.                 }
  13.             }
  14.         }
  15.         return dp[amount] > amount ? -1 : dp[amount];
  16.     }
  17. }

377 Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

题目描述

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

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

代码

  1. class Solution {
  2.     public int combinationSum4(int[] nums, int target) {
  3.         int[] dp = new int[target + 1];
  4.         dp[0] = 1;
  5.         for (int i = 1; i <= target; i++) {
  6.             for (int v : nums) {
  7.                 if (i >= v) {
  8.                     dp[i] += dp[i - v];
  9.                 }
  10.             }
  11.         }
  12.         return dp[target];
  13.     }
  14. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注