- Climbing Stairs
- Fibonacci Number
- N-th Tribonacci Number
- Min Cost Climbing Stairs
- House Robber
- Delete and Earn
- Longest Palindromic Substring
- Word Break
- Longest Palindromic Subsequence
- Edit Distance
- Minimum ASCII Delete Sum for Two Strings
- Distinct Subsequences
- Longest Increasing Subsequence
- Number of Longest Increasing Subsequence
- Maximum Length of Pair Chain
- Longest Arithmetic Subsequence of Given Difference
- Longest Arithmetic Subsequence
- Russian Doll Envelopes
- Find the Longest Valid Obstacle Course at Each Position
- Best Time to Buy and Sell Stock with Cooldown
- Best Time to Buy and Sell Stock with Transaction Fee
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Unique Binary Search Trees
- Unique Binary Search Trees II
- House Robber III
- Binary Tree Maximum Path Sum
- Solving Questions With Brainpower
- Coin Change
- Count Ways To Build Good Strings
- Decode Ways
- Minimum Cost For Tickets
- Domino and Tromino Tiling
Difficulty: Easy | LeetCode #70
Problem: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you climb to the top?
class Solution {
private int[] memo;
public int climbStairs(int n) {
memo = new int[n + 1];
return dp(n);
}
private int dp(int n) {
if (n <= 1) return 1;
if (memo[n] != 0) return memo[n];
memo[n] = dp(n - 1) + dp(n - 2);
return memo[n];
}
}class Solution {
public int climbStairs(int n) {
if (n <= 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}class Solution {
public int climbStairs(int n) {
if (n <= 1) return 1;
int prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}Difficulty: Easy | LeetCode #509
Problem: Calculate F(n) where F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).
class Solution {
private int[] memo;
public int fib(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return dp(n);
}
private int dp(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = dp(n - 1) + dp(n - 2);
return memo[n];
}
}class Solution {
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}class Solution {
public int fib(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}Difficulty: Easy | LeetCode #1137
Problem: T(n) = T(n-1) + T(n-2) + T(n-3), with T(0)=0, T(1)=1, T(2)=1.
class Solution {
private int[] memo;
public int tribonacci(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return dp(n);
}
private int dp(int n) {
if (n == 0) return 0;
if (n <= 2) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = dp(n - 1) + dp(n - 2) + dp(n - 3);
return memo[n];
}
}class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;
if (n <= 2) return 1;
int[] dp = new int[n + 1];
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
}class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;
if (n <= 2) return 1;
int a = 0, b = 1, c = 1;
for (int i = 3; i <= n; i++) {
int d = a + b + c;
a = b; b = c; c = d;
}
return c;
}
}Difficulty: Easy | LeetCode #746
Problem: Given cost[] where cost[i] is the cost at step i, find the minimum cost to reach the top (beyond last step). You can start at index 0 or 1.
class Solution {
private int[] memo;
private int[] cost;
public int minCostClimbingStairs(int[] cost) {
this.cost = cost;
int n = cost.length;
memo = new int[n];
Arrays.fill(memo, -1);
return Math.min(dp(n - 1), dp(n - 2));
}
private int dp(int i) {
if (i < 0) return 0;
if (memo[i] != -1) return memo[i];
memo[i] = cost[i] + Math.min(dp(i - 1), dp(i - 2));
return memo[i];
}
}class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < n; i++) {
dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
}
return Math.min(dp[n - 1], dp[n - 2]);
}
}class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int prev2 = cost[0], prev1 = cost[1];
for (int i = 2; i < n; i++) {
int curr = cost[i] + Math.min(prev1, prev2);
prev2 = prev1;
prev1 = curr;
}
return Math.min(prev1, prev2);
}
}Difficulty: Medium | LeetCode #198
Problem: Rob houses along a street; adjacent houses have alarms. Maximize the amount robbed without triggering alarms.
class Solution {
private int[] memo;
public int rob(int[] nums) {
memo = new int[nums.length];
Arrays.fill(memo, -1);
return dp(nums, nums.length - 1);
}
private int dp(int[] nums, int i) {
if (i < 0) return 0;
if (memo[i] != -1) return memo[i];
memo[i] = Math.max(dp(nums, i - 1), nums[i] + dp(nums, i - 2));
return memo[i];
}
}class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[n - 1];
}
}class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, num + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}Difficulty: Medium | LeetCode #740
Problem: Delete element nums[i] to earn nums[i] points; must also delete all elements equal to nums[i]-1 and nums[i]+1. Maximize total points.
class Solution {
private int[] memo;
private int[] points;
public int deleteAndEarn(int[] nums) {
int maxVal = Arrays.stream(nums).max().getAsInt();
points = new int[maxVal + 1];
for (int n : nums) points[n] += n;
memo = new int[maxVal + 1];
Arrays.fill(memo, -1);
return dp(maxVal);
}
private int dp(int i) {
if (i <= 0) return 0;
if (i == 1) return points[1];
if (memo[i] != -1) return memo[i];
memo[i] = Math.max(dp(i - 1), points[i] + dp(i - 2));
return memo[i];
}
}class Solution {
public int deleteAndEarn(int[] nums) {
int maxVal = Arrays.stream(nums).max().getAsInt();
int[] points = new int[maxVal + 1];
for (int n : nums) points[n] += n;
int[] dp = new int[maxVal + 1];
dp[1] = points[1];
for (int i = 2; i <= maxVal; i++) {
dp[i] = Math.max(dp[i - 1], points[i] + dp[i - 2]);
}
return dp[maxVal];
}
}class Solution {
public int deleteAndEarn(int[] nums) {
int maxVal = Arrays.stream(nums).max().getAsInt();
int[] points = new int[maxVal + 1];
for (int n : nums) points[n] += n;
int prev2 = 0, prev1 = points[1];
for (int i = 2; i <= maxVal; i++) {
int curr = Math.max(prev1, points[i] + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}Difficulty: Medium | LeetCode #62
Problem: Count unique paths from top-left to bottom-right of an m x n grid, moving only right or down.
class Solution {
private int[][] memo;
public int uniquePaths(int m, int n) {
memo = new int[m][n];
return dp(m - 1, n - 1);
}
private int dp(int i, int j) {
if (i == 0 || j == 0) return 1;
if (memo[i][j] != 0) return memo[i][j];
memo[i][j] = dp(i - 1, j) + dp(i, j - 1);
return memo[i][j];
}
}class Solution {
public int uniquePaths(int m, int 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 - 1][j] + dp[i][j - 1];
return dp[m - 1][n - 1];
}
}class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[j] += dp[j - 1];
return dp[n - 1];
}
}Difficulty: Medium | LeetCode #64
Problem: Find the path from top-left to bottom-right (moving right or down) in a grid that minimizes the sum of numbers along the path.
class Solution {
private int[][] memo;
private int[][] grid;
public int minPathSum(int[][] grid) {
this.grid = grid;
int m = grid.length, n = grid[0].length;
memo = new int[m][n];
for (int[] row : memo) Arrays.fill(row, -1);
return dp(m - 1, n - 1);
}
private int dp(int i, int j) {
if (i == 0 && j == 0) return grid[0][0];
if (i < 0 || j < 0) return Integer.MAX_VALUE;
if (memo[i][j] != -1) return memo[i][j];
memo[i][j] = grid[i][j] + Math.min(dp(i - 1, j), dp(i, j - 1));
return memo[i][j];
}
}class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
return dp[m - 1][n - 1];
}
}class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
dp[0] = grid[0][0];
for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
for (int i = 1; i < m; i++) {
dp[0] += grid[i][0];
for (int j = 1; j < n; j++)
dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
}
return dp[n - 1];
}
}Difficulty: Medium | LeetCode #63
Problem: Same as Unique Paths, but some cells are obstacles (obstacleGrid[i][j] == 1).
class Solution {
private int[][] memo;
private int[][] grid;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
grid = obstacleGrid;
int m = grid.length, n = grid[0].length;
memo = new int[m][n];
for (int[] row : memo) Arrays.fill(row, -1);
return dp(m - 1, n - 1);
}
private int dp(int i, int j) {
if (i < 0 || j < 0 || grid[i][j] == 1) return 0;
if (i == 0 && j == 0) return 1;
if (memo[i][j] != -1) return memo[i][j];
memo[i][j] = dp(i - 1, j) + dp(i, j - 1);
return memo[i][j];
}
}class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m && grid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && grid[0][j] == 0; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (grid[i][j] == 0)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
return dp[m - 1][n - 1];
}
}class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
int n = grid[0].length;
int[] dp = new int[n];
dp[0] = 1;
for (int[] row : grid) {
for (int j = 0; j < n; j++) {
if (row[j] == 1) dp[j] = 0;
else if (j > 0) dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}Difficulty: Medium | LeetCode #120
Problem: Find the minimum path sum from top to bottom of a triangle. At each step, move to an adjacent number in the row below.
class Solution {
private int[][] memo;
private List<List<Integer>> triangle;
public int minimumTotal(List<List<Integer>> triangle) {
this.triangle = triangle;
int n = triangle.size();
memo = new int[n][n];
for (int[] row : memo) Arrays.fill(row, Integer.MAX_VALUE);
return dp(0, 0);
}
private int dp(int row, int col) {
if (row == triangle.size()) return 0;
if (memo[row][col] != Integer.MAX_VALUE) return memo[row][col];
int curr = triangle.get(row).get(col);
memo[row][col] = curr + Math.min(dp(row + 1, col), dp(row + 1, col + 1));
return memo[row][col];
}
}class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new ArrayList<>(triangle.get(n - 1)).stream().mapToInt(i -> i).toArray();
for (int row = n - 2; row >= 0; row--)
for (int col = 0; col <= row; col++)
dp[col] = triangle.get(row).get(col) + Math.min(dp[col], dp[col + 1]);
return dp[0];
}
}Difficulty: Medium | LeetCode #931
Problem: Find the minimum sum of a falling path through matrix. A falling path moves to the next row, choosing the same or adjacent column.
class Solution {
private int[][] memo;
private int[][] matrix;
public int minFallingPathSum(int[][] matrix) {
this.matrix = matrix;
int n = matrix.length;
memo = new int[n][n];
for (int[] r : memo) Arrays.fill(r, Integer.MAX_VALUE);
int res = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) res = Math.min(res, dp(0, j));
return res;
}
private int dp(int row, int col) {
int n = matrix.length;
if (col < 0 || col >= n) return Integer.MAX_VALUE;
if (row == n - 1) return matrix[row][col];
if (memo[row][col] != Integer.MAX_VALUE) return memo[row][col];
memo[row][col] = matrix[row][col] + Math.min(dp(row + 1, col - 1),
Math.min(dp(row + 1, col), dp(row + 1, col + 1)));
return memo[row][col];
}
}class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int[] prev = matrix[0].clone();
for (int i = 1; i < n; i++) {
int[] curr = new int[n];
for (int j = 0; j < n; j++) {
int best = prev[j];
if (j > 0) best = Math.min(best, prev[j - 1]);
if (j < n - 1) best = Math.min(best, prev[j + 1]);
curr[j] = matrix[i][j] + best;
}
prev = curr;
}
int res = Integer.MAX_VALUE;
for (int v : prev) res = Math.min(res, v);
return res;
}
}Difficulty: Medium | LeetCode #221
Problem: Find the largest square containing only '1's and return its area.
class Solution {
private int[][] memo;
private char[][] matrix;
public int maximalSquare(char[][] matrix) {
this.matrix = matrix;
int m = matrix.length, n = matrix[0].length;
memo = new int[m][n];
for (int[] r : memo) Arrays.fill(r, -1);
int max = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
max = Math.max(max, dp(i, j));
return max * max;
}
private int dp(int i, int j) {
if (i < 0 || j < 0 || matrix[i][j] == '0') return 0;
if (memo[i][j] != -1) return memo[i][j];
memo[i][j] = 1 + Math.min(dp(i - 1, j), Math.min(dp(i, j - 1), dp(i - 1, j - 1)));
return memo[i][j];
}
}class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length, max = 0;
int[] dp = new int[n + 1];
int prev = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (matrix[i - 1][j - 1] == '1') {
dp[j] = 1 + Math.min(prev, Math.min(dp[j], dp[j - 1]));
max = Math.max(max, dp[j]);
} else {
dp[j] = 0;
}
prev = temp;
}
}
return max * max;
}
}Difficulty: Medium | LeetCode #5
Problem: Find the longest palindromic substring in s.
class Solution {
private Boolean[][] memo;
private String s;
public String longestPalindrome(String s) {
this.s = s;
int n = s.length();
memo = new Boolean[n][n];
int start = 0, maxLen = 1;
for (int len = 2; len <= n; len++)
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (isPalin(i, j) && len > maxLen) {
maxLen = len; start = i;
}
}
return s.substring(start, start + maxLen);
}
private boolean isPalin(int i, int j) {
if (i >= j) return true;
if (memo[i][j] != null) return memo[i][j];
memo[i][j] = s.charAt(i) == s.charAt(j) && isPalin(i + 1, j - 1);
return memo[i][j];
}
}class Solution {
public String longestPalindrome(String s) {
int n = s.length(), start = 0, maxLen = 1;
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) dp[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (len > maxLen) { maxLen = len; start = i; }
}
}
}
return s.substring(start, start + maxLen);
}
}Difficulty: Medium | LeetCode #139
Problem: Given s and a dictionary wordDict, return true if s can be segmented into space-separated dictionary words.
class Solution {
private Boolean[] memo;
private Set<String> dict;
public boolean wordBreak(String s, List<String> wordDict) {
dict = new HashSet<>(wordDict);
memo = new Boolean[s.length()];
return dp(s, 0);
}
private boolean dp(String s, int start) {
if (start == s.length()) return true;
if (memo[start] != null) return memo[start];
for (int end = start + 1; end <= s.length(); end++) {
if (dict.contains(s.substring(start, end)) && dp(s, end)) {
return memo[start] = true;
}
}
return memo[start] = false;
}
}class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(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++)
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true; break;
}
return dp[n];
}
}Difficulty: Medium | LeetCode #516
Problem: Find the longest palindromic subsequence's length in s.
class Solution {
private int[][] memo;
public int longestPalindromeSubseq(String s) {
int n = s.length();
memo = new int[n][n];
return dp(s, 0, n - 1);
}
private int dp(String s, int l, int r) {
if (l > r) return 0;
if (l == r) return 1;
if (memo[l][r] != 0) return memo[l][r];
if (s.charAt(l) == s.charAt(r))
memo[l][r] = 2 + dp(s, l + 1, r - 1);
else
memo[l][r] = Math.max(dp(s, l + 1, r), dp(s, l, r - 1));
return memo[l][r];
}
}class Solution {
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 len = 2; len <= n; len++)
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
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];
}
}class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[] dp = new int[n];
int[] prev = new int[n];
Arrays.fill(dp, 1);
for (int i = n - 2; i >= 0; i--) {
int[] curr = new int[n];
curr[i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j))
curr[j] = 2 + (j - 1 >= i + 1 ? dp[j - 1] : 0); // need full 2D for this
else
curr[j] = Math.max(dp[j], curr[j - 1]);
}
dp = curr;
}
return dp[n - 1];
}
}Note: True O(n) space optimization for interval DP requires careful diagonal traversal. The bottom-up O(n²) space solution is generally preferred for clarity.
Difficulty: Medium | LeetCode #72
Problem: Given word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 to word2.
class Solution {
private int[][] memo;
public int minDistance(String word1, String word2) {
memo = new int[word1.length() + 1][word2.length() + 1];
for (int[] r : memo) Arrays.fill(r, -1);
return dp(word1, word2, word1.length(), word2.length());
}
private int dp(String w1, String w2, int i, int j) {
if (i == 0) return j;
if (j == 0) return i;
if (memo[i][j] != -1) return memo[i][j];
if (w1.charAt(i - 1) == w2.charAt(j - 1))
memo[i][j] = dp(w1, w2, i - 1, j - 1);
else
memo[i][j] = 1 + Math.min(dp(w1, w2, i - 1, j - 1),
Math.min(dp(w1, w2, i - 1, j), dp(w1, w2, i, j - 1)));
return memo[i][j];
}
}class Solution {
public int minDistance(String w1, String w2) {
int m = w1.length(), n = w2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (w1.charAt(i - 1) == w2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
return dp[m][n];
}
}class Solution {
public int minDistance(String w1, String w2) {
int m = w1.length(), n = w2.length();
int[] dp = new int[n + 1];
for (int j = 0; j <= n; j++) dp[j] = j;
for (int i = 1; i <= m; i++) {
int prev = dp[0];
dp[0] = i;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (w1.charAt(i - 1) == w2.charAt(j - 1))
dp[j] = prev;
else
dp[j] = 1 + Math.min(prev, Math.min(dp[j], dp[j - 1]));
prev = temp;
}
}
return dp[n];
}
}Difficulty: Medium | LeetCode #712
Problem: Given s1 and s2, return the lowest ASCII sum of deleted characters to make them equal.
class Solution {
private int[][] memo;
public int minimumDeleteSum(String s1, String s2) {
memo = new int[s1.length() + 1][s2.length() + 1];
for (int[] r : memo) Arrays.fill(r, -1);
return dp(s1, s2, 0, 0);
}
private int dp(String s1, String s2, int i, int j) {
if (i == s1.length()) {
int sum = 0;
for (int k = j; k < s2.length(); k++) sum += s2.charAt(k);
return sum;
}
if (j == s2.length()) {
int sum = 0;
for (int k = i; k < s1.length(); k++) sum += s1.charAt(k);
return sum;
}
if (memo[i][j] != -1) return memo[i][j];
if (s1.charAt(i) == s2.charAt(j))
memo[i][j] = dp(s1, s2, i + 1, j + 1);
else
memo[i][j] = Math.min(s1.charAt(i) + dp(s1, s2, i + 1, j),
s2.charAt(j) + dp(s1, s2, i, j + 1));
return memo[i][j];
}
}class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[] dp = new int[n + 1];
for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] + s2.charAt(j - 1);
for (int i = 1; i <= m; i++) {
int prev = dp[0];
dp[0] += s1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[j] = prev;
else
dp[j] = Math.min(s1.charAt(i - 1) + dp[j], s2.charAt(j - 1) + dp[j - 1]);
prev = temp;
}
}
return dp[n];
}
}Difficulty: Hard | LeetCode #115
Problem: Count the number of distinct subsequences of s that equals t.
class Solution {
private long[][] memo;
public int numDistinct(String s, String t) {
memo = new long[s.length()][t.length()];
for (long[] r : memo) Arrays.fill(r, -1);
return (int) dp(s, t, 0, 0);
}
private long dp(String s, String t, int i, int j) {
if (j == t.length()) return 1;
if (i == s.length()) return 0;
if (memo[i][j] != -1) return memo[i][j];
memo[i][j] = dp(s, t, i + 1, j);
if (s.charAt(i) == t.charAt(j))
memo[i][j] += dp(s, t, i + 1, j + 1);
return memo[i][j];
}
}class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= m; i++)
for (int j = Math.min(i, n); j >= 1; j--)
if (s.charAt(i - 1) == t.charAt(j - 1))
dp[j] += dp[j - 1];
return (int) dp[n];
}
}Difficulty: Medium | LeetCode #300
Problem: Return the length of the longest strictly increasing subsequence.
class Solution {
private int[] memo;
public int lengthOfLIS(int[] nums) {
memo = new int[nums.length];
int max = 0;
for (int i = 0; i < nums.length; i++)
max = Math.max(max, dp(nums, i));
return max;
}
private int dp(int[] nums, int i) {
if (memo[i] != 0) return memo[i];
memo[i] = 1;
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
memo[i] = Math.max(memo[i], 1 + dp(nums, j));
return memo[i];
}
}class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length, max = 1;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j] + 1);
max = Math.max(max, dp[i]);
}
return max;
}
}class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = Collections.binarySearch(tails, num);
if (pos < 0) pos = -(pos + 1);
if (pos == tails.size()) tails.add(num);
else tails.set(pos, num);
}
return tails.size();
}
}Difficulty: Medium | LeetCode #673
Problem: Return the number of longest increasing subsequences.
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length, maxLen = 0, res = 0;
int[] len = new int[n], cnt = new int[n];
Arrays.fill(len, 1);
Arrays.fill(cnt, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; cnt[i] = cnt[j]; }
else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
}
}
maxLen = Math.max(maxLen, len[i]);
}
for (int i = 0; i < n; i++)
if (len[i] == maxLen) res += cnt[i];
return res;
}
}Difficulty: Medium | LeetCode #646
Problem: Given pairs [a,b], chain them where b < c for consecutive pairs [a,b], [c,d]. Find the longest chain.
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
int chains = 1, end = pairs[0][1];
for (int i = 1; i < pairs.length; i++) {
if (pairs[i][0] > end) {
chains++;
end = pairs[i][1];
}
}
return chains;
}
}class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int n = pairs.length, max = 1;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (pairs[j][1] < pairs[i][0])
dp[i] = Math.max(dp[i], dp[j] + 1);
max = Math.max(max, dp[i]);
}
return max;
}
}Difficulty: Medium | LeetCode #1218
Problem: Find the longest subsequence in arr where consecutive elements differ by exactly difference.
class Solution {
public int longestSubsequence(int[] arr, int difference) {
Map<Integer, Integer> dp = new HashMap<>();
int res = 1;
for (int num : arr) {
int prev = dp.getOrDefault(num - difference, 0);
dp.put(num, prev + 1);
res = Math.max(res, dp.get(num));
}
return res;
}
}Difficulty: Medium | LeetCode #1027
Problem: Find the longest arithmetic subsequence in nums.
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length, res = 2;
Map<Integer, Integer>[] dp = new HashMap[n];
for (int i = 0; i < n; i++) dp[i] = new HashMap<>();
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
int prev = dp[j].getOrDefault(diff, 1);
dp[i].put(diff, prev + 1);
res = Math.max(res, dp[i].get(diff));
}
}
return res;
}
}Difficulty: Hard | LeetCode #354
Problem: Count the maximum number of envelopes that can be Russian dolled (both width and height must be strictly greater).
class Solution {
public int maxEnvelopes(int[][] envelopes) {
// Sort by width asc; if equal width, sort height desc to avoid using same width twice
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
// LIS on heights
List<Integer> tails = new ArrayList<>();
for (int[] e : envelopes) {
int h = e[1];
int pos = Collections.binarySearch(tails, h);
if (pos < 0) pos = -(pos + 1);
if (pos == tails.size()) tails.add(h);
else tails.set(pos, h);
}
return tails.size();
}
}Difficulty: Hard | LeetCode #1964
Problem: For each index i, find the length of the longest non-decreasing subsequence ending at obstacles[i].
class Solution {
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
int n = obstacles.length;
int[] ans = new int[n];
List<Integer> tails = new ArrayList<>();
for (int i = 0; i < n; i++) {
int h = obstacles[i];
// Find first position > h (non-decreasing, so allow equal)
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails.get(mid) <= h) lo = mid + 1;
else hi = mid;
}
ans[i] = lo + 1;
if (lo == tails.size()) tails.add(h);
else tails.set(lo, h);
}
return ans;
}
}Difficulty: Medium | LeetCode #1143
Problem: Return the length of the longest common subsequence of text1 and text2.
class Solution {
private int[][] memo;
public int longestCommonSubsequence(String text1, String text2) {
memo = new int[text1.length()][text2.length()];
for (int[] r : memo) Arrays.fill(r, -1);
return dp(text1, text2, 0, 0);
}
private int dp(String s1, String s2, int i, int j) {
if (i == s1.length() || j == s2.length()) return 0;
if (memo[i][j] != -1) return memo[i][j];
if (s1.charAt(i) == s2.charAt(j))
memo[i][j] = 1 + dp(s1, s2, i + 1, j + 1);
else
memo[i][j] = Math.max(dp(s1, s2, i + 1, j), dp(s1, s2, i, j + 1));
return memo[i][j];
}
}class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), 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 - 1][j], dp[i][j - 1]);
}
return dp[m][n];
}
}class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (text1.charAt(i - 1) == text2.charAt(j - 1))
dp[j] = prev + 1;
else
dp[j] = Math.max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[n];
}
}Difficulty: Medium | LeetCode #1035
Problem: Draw connecting lines between equal-valued elements in nums1 and nums2 without crossing. Maximize the number of lines. (This is equivalent to LCS.)
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (nums1[i - 1] == nums2[j - 1])
dp[j] = prev + 1;
else
dp[j] = Math.max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[n];
}
}Difficulty: Hard | LeetCode #1312
Problem: Return the minimum number of insertions to make s a palindrome. (Answer = n - LPS length)
class Solution {
public int minInsertions(String s) {
int n = s.length();
// LCS of s and reverse(s) gives Longest Palindromic Subsequence
String rev = new StringBuilder(s).reverse().toString();
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (s.charAt(i - 1) == rev.charAt(j - 1))
dp[j] = prev + 1;
else
dp[j] = Math.max(dp[j], dp[j - 1]);
prev = temp;
}
}
return n - dp[n];
}
}Difficulty: Medium | LeetCode #309
Problem: After selling, you must wait 1 day (cooldown). Maximize profit.
class Solution {
public int maxProfit(int[] prices) {
int held = Integer.MIN_VALUE, sold = 0, rest = 0;
for (int price : prices) {
int prevSold = sold;
sold = held + price;
held = Math.max(held, rest - price);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}
}class Solution {
private int[][] memo;
public int maxProfit(int[] prices) {
memo = new int[prices.length][2];
for (int[] r : memo) Arrays.fill(r, -1);
return dp(prices, 0, 0);
}
// state: 0 = can buy, 1 = can sell
private int dp(int[] prices, int i, int state) {
if (i >= prices.length) return 0;
if (memo[i][state] != -1) return memo[i][state];
int doNothing = dp(prices, i + 1, state);
int doSomething;
if (state == 0) // buy
doSomething = -prices[i] + dp(prices, i + 1, 1);
else // sell with cooldown
doSomething = prices[i] + dp(prices, i + 2, 0);
memo[i][state] = Math.max(doNothing, doSomething);
return memo[i][state];
}
}Difficulty: Medium | LeetCode #714
Problem: Unlimited transactions, but each sale costs fee. Maximize profit.
class Solution {
public int maxProfit(int[] prices, int fee) {
int held = -prices[0], cash = 0;
for (int i = 1; i < prices.length; i++) {
cash = Math.max(cash, held + prices[i] - fee);
held = Math.max(held, cash - prices[i]);
}
return cash;
}
}Difficulty: Hard | LeetCode #123
Problem: At most 2 transactions. Maximize profit.
class Solution {
public int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, sell1 = 0;
int buy2 = Integer.MIN_VALUE, sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}
}Difficulty: Hard | LeetCode #188
Problem: At most k transactions. Maximize profit.
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) {
int profit = 0;
for (int i = 1; i < n; i++)
profit += Math.max(0, prices[i] - prices[i - 1]);
return profit;
}
int[] buy = new int[k + 1], sell = new int[k + 1];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int price : prices) {
for (int t = k; t >= 1; t--) {
sell[t] = Math.max(sell[t], buy[t] + price);
buy[t] = Math.max(buy[t], sell[t - 1] - price);
}
}
return sell[k];
}
}Difficulty: Medium | LeetCode #96
Problem: Return the number of structurally unique BSTs with n nodes (Catalan numbers).
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
dp[i] += dp[j - 1] * dp[i - j];
return dp[n];
}
}class Solution {
private Map<Integer, Integer> memo = new HashMap<>();
public int numTrees(int n) {
if (n <= 1) return 1;
if (memo.containsKey(n)) return memo.get(n);
int sum = 0;
for (int i = 1; i <= n; i++)
sum += numTrees(i - 1) * numTrees(n - i);
memo.put(n, sum);
return sum;
}
}Difficulty: Medium | LeetCode #95
Problem: Return all structurally unique BSTs with values 1..n.
class Solution {
private Map<String, List<TreeNode>> memo = new HashMap<>();
public List<TreeNode> generateTrees(int n) {
return generate(1, n);
}
private List<TreeNode> generate(int start, int end) {
List<TreeNode> res = new ArrayList<>();
if (start > end) { res.add(null); return res; }
String key = start + "," + end;
if (memo.containsKey(key)) return memo.get(key);
for (int root = start; root <= end; root++) {
for (TreeNode left : generate(start, root - 1))
for (TreeNode right : generate(root + 1, end))
res.add(new TreeNode(root, left, right));
}
memo.put(key, res);
return res;
}
}Difficulty: Medium | LeetCode #337
Problem: Rob houses in a binary tree; cannot rob directly linked nodes. Maximize money.
class Solution {
public int rob(TreeNode root) {
int[] res = dp(root);
return Math.max(res[0], res[1]);
}
// returns [maxWithoutRoot, maxWithRoot]
private int[] dp(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dp(node.left);
int[] right = dp(node.right);
int withRoot = node.val + left[0] + right[0];
int withoutRoot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{withoutRoot, withRoot};
}
}Difficulty: Hard | LeetCode #124
Problem: Find the maximum path sum in a binary tree (path can start and end at any node).
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
gain(root);
return maxSum;
}
private int gain(TreeNode node) {
if (node == null) return 0;
int leftGain = Math.max(gain(node.left), 0);
int rightGain = Math.max(gain(node.right), 0);
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
return node.val + Math.max(leftGain, rightGain);
}
}Difficulty: Medium | LeetCode #279
Problem: Find the least number of perfect squares that sum to n.
class Solution {
private int[] memo;
public int numSquares(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return dp(n);
}
private int dp(int n) {
if (n == 0) return 0;
if (memo[n] != -1) return memo[n];
memo[n] = Integer.MAX_VALUE;
for (int i = 1; i * i <= n; i++)
memo[n] = Math.min(memo[n], 1 + dp(n - i * i));
return memo[n];
}
}class Solution {
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], dp[i - j * j] + 1);
return dp[n];
}
}Difficulty: Medium | LeetCode #518
Problem: Return the number of combinations of coins that make up amount.
class Solution {
private int[][] memo;
public int change(int amount, int[] coins) {
memo = new int[coins.length][amount + 1];
for (int[] r : memo) Arrays.fill(r, -1);
return dp(coins, 0, amount);
}
private int dp(int[] coins, int i, int rem) {
if (rem == 0) return 1;
if (i == coins.length || rem < 0) return 0;
if (memo[i][rem] != -1) return memo[i][rem];
memo[i][rem] = dp(coins, i + 1, rem) + dp(coins, i, rem - coins[i]);
return memo[i][rem];
}
}class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins)
for (int j = coin; j <= amount; j++)
dp[j] += dp[j - coin];
return dp[amount];
}
}Difficulty: Medium | LeetCode #377
Problem: Return the number of ordered combinations (permutations) of nums that sum to target.
class Solution {
private int[] memo;
public int combinationSum4(int[] nums, int target) {
memo = new int[target + 1];
Arrays.fill(memo, -1);
return dp(nums, target);
}
private int dp(int[] nums, int rem) {
if (rem == 0) return 1;
if (rem < 0) return 0;
if (memo[rem] != -1) return memo[rem];
memo[rem] = 0;
for (int num : nums)
memo[rem] += dp(nums, rem - num);
return memo[rem];
}
}class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++)
for (int num : nums)
if (i >= num) dp[i] += dp[i - num];
return dp[target];
}
}Difficulty: Medium | LeetCode #474
Problem: Given binary strings, find the max subset size fitting within m zeros and n ones budget.
class Solution {
private int[][][] memo;
public int findMaxForm(String[] strs, int m, int n) {
memo = new int[strs.length][m + 1][n + 1];
for (int[][] a : memo) for (int[] b : a) Arrays.fill(b, -1);
return dp(strs, 0, m, n);
}
private int dp(String[] strs, int i, int m, int n) {
if (i == strs.length) return 0;
if (memo[i][m][n] != -1) return memo[i][m][n];
int zeros = (int) strs[i].chars().filter(c -> c == '0').count();
int ones = strs[i].length() - zeros;
int skip = dp(strs, i + 1, m, n);
int take = (m >= zeros && n >= ones) ? 1 + dp(strs, i + 1, m - zeros, n - ones) : 0;
memo[i][m][n] = Math.max(skip, take);
return memo[i][m][n];
}
}class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) {
int zeros = (int) s.chars().filter(c -> c == '0').count();
int ones = s.length() - zeros;
for (int i = m; i >= zeros; i--)
for (int j = n; j >= ones; j--)
dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
}
return dp[m][n];
}
}Difficulty: Medium | LeetCode #2140
Problem: Each question [points, brainpower]: if you solve it, earn points but skip next brainpower questions. Maximize total points.
class Solution {
private long[] memo;
public long mostPoints(int[][] questions) {
memo = new long[questions.length];
Arrays.fill(memo, -1);
return dp(questions, 0);
}
private long dp(int[][] q, int i) {
if (i >= q.length) return 0;
if (memo[i] != -1) return memo[i];
long solve = q[i][0] + dp(q, i + q[i][1] + 1);
long skip = dp(q, i + 1);
memo[i] = Math.max(solve, skip);
return memo[i];
}
}class Solution {
public long mostPoints(int[][] questions) {
int n = questions.length;
long[] dp = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
int next = i + questions[i][1] + 1;
long solve = questions[i][0] + (next < n ? dp[next] : 0);
dp[i] = Math.max(dp[i + 1], solve);
}
return dp[0];
}
}Difficulty: Medium | LeetCode #322
Problem: Find the fewest number of coins needed to make amount. Return -1 if impossible.
class Solution {
private int[] memo;
public int coinChange(int[] coins, int amount) {
memo = new int[amount + 1];
Arrays.fill(memo, -1);
int res = dp(coins, amount);
return res == Integer.MAX_VALUE ? -1 : res;
}
private int dp(int[] coins, int rem) {
if (rem == 0) return 0;
if (rem < 0) return Integer.MAX_VALUE;
if (memo[rem] != -1) return memo[rem];
memo[rem] = Integer.MAX_VALUE;
for (int coin : coins) {
int sub = dp(coins, rem - coin);
if (sub != Integer.MAX_VALUE)
memo[rem] = Math.min(memo[rem], sub + 1);
}
return memo[rem];
}
}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];
}
}Difficulty: Medium | LeetCode #2466
Problem: Build strings of length in [low, high] using zero zeros or one ones at each step. Count valid strings mod 1e9+7.
class Solution {
public int countGoodStrings(int low, int high, int zero, int one) {
int MOD = 1_000_000_007;
int[] dp = new int[high + 1];
dp[0] = 1;
int res = 0;
for (int i = 1; i <= high; i++) {
if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD;
if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
if (i >= low) res = (res + dp[i]) % MOD;
}
return res;
}
}Difficulty: Medium | LeetCode #91
Problem: A string of digits maps to letters (1→A, 26→Z). Count the total number of ways to decode s.
class Solution {
private int[] memo;
public int numDecodings(String s) {
memo = new int[s.length()];
Arrays.fill(memo, -1);
return dp(s, 0);
}
private int dp(String s, int i) {
if (i == s.length()) return 1;
if (s.charAt(i) == '0') return 0;
if (memo[i] != -1) return memo[i];
int res = dp(s, i + 1);
if (i + 1 < s.length()) {
int twoDigit = Integer.parseInt(s.substring(i, i + 2));
if (twoDigit <= 26) res += dp(s, i + 2);
}
memo[i] = res;
return memo[i];
}
}class Solution {
public int numDecodings(String s) {
int n = s.length();
int next2 = 1, next1 = s.charAt(n - 1) == '0' ? 0 : 1;
for (int i = n - 2; i >= 0; i--) {
int curr = s.charAt(i) == '0' ? 0 : next1;
int twoDigit = Integer.parseInt(s.substring(i, i + 2));
if (twoDigit <= 26) curr += next2;
next2 = next1;
next1 = curr;
}
return next1;
}
}Difficulty: Medium | LeetCode #983
Problem: Travel on certain days; buy 1-day, 7-day, or 30-day passes. Minimize total cost.
class Solution {
private int[] memo;
private int[] days, costs;
private int[] durations = {1, 7, 30};
public int mincostTickets(int[] days, int[] costs) {
this.days = days; this.costs = costs;
memo = new int[days[days.length - 1] + 1];
Arrays.fill(memo, -1);
return dp(0);
}
private int dp(int dayIdx) {
if (dayIdx >= days.length) return 0;
if (memo[dayIdx] != -1) return memo[dayIdx];
memo[dayIdx] = Integer.MAX_VALUE;
int j = dayIdx;
for (int k = 0; k < 3; k++) {
while (j < days.length && days[j] < days[dayIdx] + durations[k]) j++;
memo[dayIdx] = Math.min(memo[dayIdx], costs[k] + dp(j));
j = dayIdx;
}
return memo[dayIdx];
}
}class Solution {
public int mincostTickets(int[] days, int[] costs) {
Set<Integer> travelDays = new HashSet<>();
for (int d : days) travelDays.add(d);
int lastDay = days[days.length - 1];
int[] dp = new int[lastDay + 1];
for (int i = 1; i <= lastDay; i++) {
if (!travelDays.contains(i)) { dp[i] = dp[i - 1]; continue; }
dp[i] = Math.min(dp[i - 1] + costs[0],
Math.min(dp[Math.max(0, i - 7)] + costs[1],
dp[Math.max(0, i - 30)] + costs[2]));
}
return dp[lastDay];
}
}Difficulty: Medium | LeetCode #790
Problem: Count the number of ways to tile a 2 x n board with dominoes and trominoes. Return answer mod 1e9+7.
class Solution {
public int numTilings(int n) {
int MOD = 1_000_000_007;
if (n == 1) return 1;
long[] dp = new long[n + 1];
dp[0] = 1; dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++)
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
return (int) dp[n];
}
}Recurrence explanation:
dp[i] = 2*dp[i-1] + dp[i-3]. This accounts for adding a vertical domino (dp[i-1]), two horizontal dominoes (dp[i-2]absorbed into2*dp[i-1]), and tromino fills for partial states (dp[i-3]).