-
Unified Dimensional
- 70 Climbing Stairs
- 91 Decode Ways
- 120 Triangle
- 139 Word Break
- 140 Word Break II
- 198 House Robber
- 213 House Robber II
- 279 Perfect Squares
- 263 Ugly Number
- 264 Ugly Number II
-
Two-dimensional
-
Three-dimensional
- 87 Scramble String
980 Unique Paths III - 741 Cherry Pickup
- 87 Scramble String
[Unified Dimensional]
#70 Climbing Stairs
- Sol
public int climbStairs(int n) {
if(n <= 2) return n;
int i1 = 1, i2 = 2;
for(int i = 3; i <= n; i++){
int tmp = i1;
i1 = i2;
i2 = tmp + i1;
}
return i2;
}
#91 Decode Ways
-
Sol
case: 含有10
public int numDecodings(String s) {
char[] ch = s.toCharArray();
if(ch[0] == '0') return 0;
if(ch.length < 2) return 1;
int n = s.length();
int i1 = 1, i2 = (ch[1] == 0 ? 0 : 1);
int var = (ch[0]-'0') * 10 + (ch[1] - '0');
if(var%10==0) i2 = 0;
if(var >= 10 && var <= 26) i2++;
for(int i = 2; i < n; i++){
int tmp = (ch[i] == 0 ? 0 : i2);
var = (ch[i-1]-'0') * 10 + (ch[i]-'0');
if(var%10==0) tmp = 0;
if(var >= 10 && var <= 26) tmp += i1;
i1 = i2;
i2 = tmp;
}
return i2;
}
#120 Triangle
- Sol Bottom-up
public int minimumTotal(List<List<Integer>> triangle) {
int row = triangle.size();
int last_row_col = triangle.get(row-1).size();
int[] dp = new int[last_row_col];
for(int i = 0; i < last_row_col; i++){
dp[i] = triangle.get(row-1).get(i);
}
for(int i = row-2; i >= 0; i--){
for(int j = 0; j <= i; j++){
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
}
}
return dp[0];
}
#139 Word Break
- Sol
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++){
String sub = s.substring(j, i);
if(wordDict.contains(sub) && dp[j]){
dp[i] = true;
break;
}
}
}
return dp[n];
}
#140 Word Break II
- Sol right-left
Map<Integer, List<String>> map; //index, res
Set<String> dict;
public List<String> wordBreak(String s, List<String> wordDict) {
map = new HashMap<>();
dict = new HashSet<>();
for(String sh: wordDict) dict.add(sh);
return help(s, s.length());
}
public List<String> help(String s, int end){
List<String> res = new ArrayList<>();
if(end == 0){
res.add("");
return res;
}
if(map.containsKey(end)) return map.get(end);
for(int i = 0; i < end; i++){
String sub = s.substring(i, end);
if(dict.contains(sub)){
List<String> next = help(s, i);
for(String str: next){
res.add((str.length()==0)?sub : str + " " + sub);
}
}
}
map.put(end, res);
return res;
}
#198 House Robber
- Sol
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 i1 = nums[0], i2 = Math.max(nums[0], nums[1]);
int n = nums.length;
for(int i = 2; i < n; i++){
int tmp = Math.max(i1 + nums[i], i2);
i1 = i2;
i2 = tmp;
}
return i2;
}
#213 House Robber II
- Sol
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 a = help(nums, 0, nums.length-1);
int b = help(nums, 1, nums.length-1);
return Math.max(a, b);
}
public int help(int[] nums, int s, int len) {
if(len == 2) return Math.max(nums[s], nums[s+1]);
int i1 = nums[s], i2 = Math.max(nums[s], nums[s+1]);
for(int i = s+2; i < s+len; i++){
int tmp = Math.max(i1 + nums[i], i2);
i1 = i2;
i2 = tmp;
}
return i2;
}
#279 Perfect Squares
-
Sol DP
dp[0] = {0} = 1
dp[1] = {1} = 1
dp[2] = {1, 1} = 2
dp[3] = {1, 1, 1} = 3
dp[4] = {4} = 1
dp[5] = {4, 1} = 2
dp[n] = Min(1+ dp[n - i * i]) for i * i <= n && i = 1,2...n
public int numSquares(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j*j <= i; j++){
dp[i] = Math.min(dp[i], 1 + dp[i-j*j]);
}
}
return dp[n];
}
#263 Ugly Number
easy
- Sol
public boolean isUgly(int num) {
if(num <= 0) return false;
if(num == 1) return true;
while(num % 2 == 0) num /= 2;
while(num % 3 == 0) num /= 3;
while(num % 5 == 0) num /= 5;
return num == 1;
}
#264 Ugly Number II
-
Sol
x=y=z=1; k=1
k is ugly number: k = 2x + 3y + 5z;
dp[++k] = min(2x, 3y, 5z)
更新xyz
public int nthUglyNumber(int n) {
int p2 = 1, p3 = 1, p5 = 1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = Math.min(Math.min(2 * dp[p2], 3 * dp[p3]), 5 * dp[p5]);
if(dp[i] == 2 * dp[p2]) p2++;
if(dp[i] == 3 * dp[p3]) p3++;
if(dp[i] == 5 * dp[p5]) p5++;
}
return dp[n];
}
[Two-dimensional]
#516 Longest Palindromic Subsequence
-
Sol
dp[i][j] denotes s[i...j] longest length of the Palindromic Subsequence.
base case: dp[i][i] = 1
if s.charAt(i) == s.charAt(j)
dp[i][j] = 2 + dp[i+1][j-1]
else dp[i][j] = max(dp[i + 1][j], dp[i][j-1])
return dp[0][len-1]
i 從后往前，j從i往后
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++) dp[i][i] = 1;
for(int i = n-1; i >= 0; i--){
for(int j = i+1; j < n; j++){
if(s.charAt(i) == s.charAt(j))
dp[i][j] = 2 + dp[i+1][j-1];
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][n-1];
}
#97 Interleaving String
-
Sol
boolean dp[i][j] denotes whether s1[0..i] and s2[0...j] make the string s3[0..i+j]
base case:
dp[0][0] = T
dp[0][j] = (s2[j-1] == s3[i+j-1] && dp[0][j-1])
dp[i][0] = (s1[i-1] == s3[i+j-1] && dp[i-1][0])
Iterative:
if(s1[i] != s3[i+j] && s2[j] != s3[i+j]) return false
else if(s1[i-1] == s3[i+j-1]) dp[i][j] = dp[i-1][j]
else if(s2[j-1] == s3[i+j-1]) dp[i][j] = dp[i][j-1]
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length()) {
return false;
}
int n1 = s1.length(), n2 = s2.length();
boolean[][] dp = new boolean[n1+1][n2+1];
//dp[0][0] = true;
for(int i = 0; i <= n1; i++){
for(int j = 0; j <= n2; j++){
if(i == 0 && j == 0)
dp[0][0] = true;
else if(i == 0)
dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
else if(j == 0)
dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);
else
dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i + j-1)
|| dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i + j-1);
}
}
return dp[n1][n2];
}
#62 Unique Paths
-
Sol
dp[i][j] denotes the unique path from (0,0) to (i,j)
--base case:
dp[0][0] = 1;
dp[0][j] = 1;
dp[i][0] =1;
--Iterative:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
--return
dp[n-1][m-1]
public int uniquePaths(int m, int n) {
int[][] dp = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 || j == 0) dp[i][j] = 1;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
#63 Unique Paths II
-
Sol
dp[i][j] denotes the unique path from (0,0) to (i,j)
--base case:
dp[0][0] = obstacleGrid[0][j] == 1 ? 0 : 1;
dp[0][j] = (obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1]);
dp[i][0] = (obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0]);
--Iterative:
dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1]
--return
dp[n-1][m-1]
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[][] dp = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i==0 && j == 0) dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : 1;
else if(i == 0) dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i][j-1];
else if(j == 0) dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j];
else dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
#64 Minimum Path Sum
-
Sol
dp[i][j] denotes the Minimum Path Sum from (0,0) to (i,j)
--base case:
dp[0][0] = grid[i][j];
dp[0][j] = dp[0][j-1] + grid[0][j];
dp[i][0] = dp[i-1][0] + + grid[i][0];
--Iterative:
dp[i][j] = Min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
--return
dp[n-1][m-1]
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i==0 && j==0) dp[i][j] = grid[i][j];
else if(i == 0) dp[i][j] = dp[0][j-1] + grid[0][j];
else if(j == 0) dp[i][j] = dp[i-1][0] + grid[i][0];
else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[n-1][m-1];
}
#72 Edit Distance
-
Sol
dp[i][j] denotes the edit distance from word1[0...i) and word2[0...j)
--base case:
dp[0][0] = 0;
dp[0][j] = j;
dp[i][0] = i;
--Iterative:
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1]
else
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
--return
dp[n][m]
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
int[][] dp = new int[n+1][m+1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if(i == 0) dp[i][j] = j;
else if(j == 0) dp[i][j] = i;
else if(word1.charAt(i-1) == word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j]);
}
}
return dp[n][m];
}
#10 Regular Expression Matching
-
Sol
dp[i][j] denotes whether there is a Regular Expression Matching between s[i...) and word2[j...)
--base case:
dp[n][m] = true
--Iterative:
pre_check = word2[j] == word1[i] || word2[j] == "."
if(word2[j+1] != "*") dp[i][j] = pre_check && dp[i+1][j+1];
else dp[i][j] = pre_check && dp[i+1][j] || dp[i][j+2];
--return:
dp[0][0]
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n+1][m+1];
dp[n][m] = true;
for(int i = n; i >= 0; i--){
for(int j = m-1; j >= 0; j--){
boolean pre = i < n && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if(j+1 < m && p.charAt(j+1) == '*')
dp[i][j] = dp[i][j+2] || pre && dp[i+1][j];
else
dp[i][j] = pre && dp[i+1][j+1];
}
}
return dp[0][0];
}
#221 Maximal Square
-
Sol
dp[i][j] denotes the side length of the maximum square which the right bottom corner is(i,j)
--base case:
dp[0][0] = matrix[i][j]
dp[0][j] = matrix[i][j]
dp[i][0] =matrix[i][j]
--Iterative:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
max_area = max(max_area, dp[i][j] ^2)
--return:
renew the largest square while iterative
max_area
public int maximalSquare(char[][] matrix) {
int n = matrix.length;
int m = n == 0 ? 0 : matrix[0].length;
int[][] dp = new int[n][m];
int max_area = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 || j == 0) dp[i][j] = matrix[i][j] - 48;
else if(matrix[i][j] == '1'){
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
max_area = Math.max(dp[i][j] * dp[i][j], max_area);
}
}
return max_area;
}
#322 Coin Change
-
Sol
dp[i] denotes the minimum number of coins that make up number i
--base case:
dp[0] = 0;
--iterative:
dp[i] = min(dp[i-c]) + 1 for c in coin[];
--return
dp[n-1]
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-coin] + 1, dp[i]);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
#787 Cheapest Flights Within K Stops
-
Sol
dp[i][j] denotes the Cheapest Flights from start to j within i stops
--base case:
dp[i][src] = 0
--iterative:
for i in (1...k+1]
for each flight f
dp[i][f[1]] = min(dp[i][f[1]], dp[i-1][f[0]] + f[2])
--return
dp[k+1][dst]
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
double[][] dp = new double[K+2][n];
for(double[] row:dp) Arrays.fill(row, 1e9);
dp[0][src] = 0;
for(int i = 1; i <= K+1; i++){
dp[i][src] = 0;
for(int j = 0; j < flights.length; j++){
dp[i][flights[j][1]] = Math.min(dp[i][flights[j][1]], dp[i-1][flights[j][0]] + flights[j][2]);
}
}
return dp[K+1][dst] >= 1e9? -1 : (int)dp[K+1][dst];
}
double因?yàn)镮nteger會有錯誤
#1035 Uncrossed Lines
-
Sol
dp[i][j] denotes the number of Uncrossed Lines between A[0...i-1] and B[0...j-1]
--base case
dp[0][0] = 0
dp[0][j] = 0
dp[i][0] = 0
--iterative:
if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = MAX(dp[i-1][j], dp[i][j-1])
--return
dp[n][m]
public int maxUncrossedLines(int[] A, int[] B) {
int n = A.length, m = B.length;
int[][] dp = new int[n+1][m+1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if(i == 0 || j == 0) dp[i][j] = 0;
else{
if(A[i-1] == B[j-1]) 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[n][m];
}
[Three-dimensional]
#87 Scramble String
-
Sol
dp[i][j][k] denotes whether s2[j...j+k] is the scramble string of s1[i...i+k]. (k is the length)
--base case:
dp[i][j][0] = true
dp[i][j][1] = s1[i] == s2[j]
--Iterative:
for i, j, k
for m in (0...k):
dp[i][j][k] = dp[i][j][m] && dp[i+m][j+m][k-m]
|| dp[i][j+k-m][m] && dp[i+m][j][k-m]
--return:
dp[0][0][len]
public boolean isScramble(String s1, String s2) {
int len = s1.length();
boolean[][][] dp = new boolean[len][len][len+1];
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
}
}
for(int k = 2; k <= len; k++){
for(int i = 0; i <= len-k; i++){
for(int j = 0; j <= len-k; j++){
for(int m = 1; m < k; m++)
if(dp[i][j][m] && dp[i+m][j+m][k-m]
|| dp[i][j+k-m][m] && dp[i+m][j][k-m]){
dp[i][j][k] = true;
break;
}
}
}
}
return dp[0][0][len];
}
DFS會更快
#980 Unique Paths III
- Sol
#741 Cherry Pickup
-
Sol
dp[r1][c1][c2] denotes the max cherry we can pick up from (r1, c1) to (n, n) and from(r1+c1-c2, c2) to (n, n)
--base case:
dp[n-1][n-1][n-1] = grid[n-1][n-1]
--itertive
dp[r][i][j] = grid[r][i] == 1 ? 1:0 + grid[r+i-j][j] == 1? 1: 0
+MAX(
dp[r][i+1][j+1]
dp[r+1][i][j]
dp[r+1][i][j+1]
dp[r][i+1][j]
)
--return
dp[0][0][0]
int[][][] dp;
public int cherryPickup(int[][] grid) {
int n = grid.length;
dp = new int[n][n][n];
for (int[][] layer: dp)
for (int[] row: layer)
Arrays.fill(row, Integer.MIN_VALUE);
return Math.max(0, help(grid, 0, 0, 0));
}
public int help(int[][] grid, int r1, int c1, int c2){
int r2 = r1 + c1 - c2;
int n = grid.length;
if(r1 == n || r2 == n || c1 == n || c2 == n) return -999999;
if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -999999;
if(r1 == n-1 && c1 == n-1) return grid[r1][c1]; // base case
if(dp[r1][c1][c2] != Integer.MIN_VALUE) return dp[r1][c1][c2];
int res = grid[r1][c1] == 1 ? 1 :0;
if(c1 != c2) res += grid[r2][c2] == 1 ? 1 :0;
res += Math.max(
Math.max(help(grid,r1, c1+1, c2+1), help(grid,r1+1, c1, c2+1)),
Math.max(help(grid,r1, c1+1, c2), help(grid,r1+1, c1, c2))
);
dp[r1][c1][c2] = res;
return res;
}
