Dynamic Programing
https://leetcode.com/discuss/general-discussion/491522/dynamic-programming-questions-thread. https://www.freecodecamp.org/news/follow-these-steps-to-solve-any-dynamic-programming-interview-problem-cc
class Solution {
public:
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int one = 0, two = 1, curt = 1;
for (int i = 2; i <= n; ++i) {
curt = one + two;
one = two;
two = curt;
}
return curt;
}
};dp[i] = dp[i - 1] + dp[i - 2]
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}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 j : nums) {
if (i - j >= 0) {
dp[i] += dp[i - j];
}
}
}
return dp[target];
} initialization: dp[0][0] = 1, dp[i][j] = 1 when i == 0 or j == 0
transition: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}When obstacle[i][j] == 1, there is no way to reach to that grid, which means dp[i][j] = 0.
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
dp[0][0] = 1;
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] != 1) {
dp[i][0] = dp[i - 1][0];
}
}
for (int i = 1; i < n; i++) {
if (obstacleGrid[0][i] != 1) {
dp[0][i] = dp[0][i - 1];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}Transition: dp[i] is the max value of get max from i - 2 plus the current one, and the max of i - 2 (not choose the current one) : dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
Initialization: dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1])
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0], nums[1]);
int[] dp = new int[n];
if (n == 1) return nums[0];
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 - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}Do the same calculation as 198 but in two different ranges:
0 to n - 2
1 to n - 1
Get the max of the dp result of both ranges.
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0], nums[1]);
return Math.max(robhelper(nums, 0, n - 2), robhelper(nums, 1, n - 1));
}
private int robhelper(int[] nums, int start, int end) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int nottakelast = nums[start];
int takelast = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = Math.max(nottakelast + nums[i], takelast);
nottakelast = takelast;
takelast = temp;
}
return Math.max(nottakelast, takelast);
}DP on Tree. Bottom up traversal. Keep the max result at each node. There are two options to get the best solution at the current node:
take self value: but not take the value from left and right child
not take self value: only take max of left child and max of right child.
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}
private int[] helper(TreeNode curt) {
if (curt == null) return new int[]{0, 0};
int[] left = helper(curt.left);
int[] right = helper(curt.right);
int takeself = left[1] + right[1] + curt.val;
int nottakeself = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{takeself, nottakeself};
}The maximal square is determined from its shortest edge at dp[i][j]. For example, the edge of:
111
110
gives dp result:
1 2 3
1 2 0
In this case
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
res = Math.max(res, dp[i][j]);
}
}
}
return res * res;
}public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
for (int i = 1; i < len; i++) {
for (int j = 0; j < triangle.get(i).size(); j++) {
int LEFT = j > 0 ? triangle.get(i - 1).get(j - 1) : Integer.MAX_VALUE;
int RIGHT = j < triangle.get(i - 1).size() ? triangle.get(i - 1).get(j) : Integer.MAX_VALUE;
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(LEFT, RIGHT));
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < triangle.get(len - 1).size(); i++) min = Math.min(min, triangle.get(len - 1).get(i));
return min;
}dp[i] : max contiguous subarray sum at i
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
max = Math.max(max, dp[i]);
}
return max;
}dp[i + k] : can jump to i + k position
dp[i + k] = dp[i] + k
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 0; i < n; i++) {
if (dp[i]) {
for (int k = 0; k <= nums[i]; k++) {
if (i + k == n - 1) return true;
dp[i + k] = true;
}
}
}
return dp[n - 1];
}int jump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= nums[i] && j + i < n; ++j) {
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
}
return dp[n - 1];
}Either move down or right, which means it comes from left and up. Find the minimum from the left and up, add to the curt grid.
T: O(m * n) S: O(1)
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0];
}
for (int i = 1; i < n; i++) {
grid[0][i] += grid[0][i - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}Get min on each grid.
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
int n = costs.length;
for (int i = 1; i < n; i++) {
costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
}
int min = Integer.MAX_VALUE;
for (int k = 0; k < 3; k++) {
min = Math.min(min, costs[n - 1][k]);
}
return min;
}Use two pointers to store the min and second min on the node.
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int colors = costs[0].length;
int min1 = -1;
int min2 = -1;
for (int i = 0; i < costs.length; i++) {
int last1 = min1;
int last2 = min2;
min1 = -1;
min2 = -1;
for (int k = 0; k < colors; k++) {
if (k != last1) {
costs[i][k] += last1 == -1 ? 0 : costs[i - 1][last1];
} else {
costs[i][k] += last2 == -1 ? 0 : costs[i - 1][last2];
}
if (min1 == -1 || costs[i][k] < costs[i][min1]) {
min2 = min1;
min1 = k;
} else if (min2 == -1 || costs[i][k] < costs[i][min2]) {
min2 = k;
}
}
}
return costs[costs.length - 1][min1];
}public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int c : coins) {
if (i - c >= 0 && dp[i - c] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i - c] + 1, dp[i]);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])
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] = Math.min(dp[i - 1] + cost[i],
dp[i - 2] + cost[i]);
}
return Math.min(dp[n - 1], dp[n - 2]);
}dp[i][j] : the number of possible ways to roll j dices so the sum of the face up numbers equals i
dp[i][j] += dp[i - face][j - 1] where 1 <= face <= f and i - d >= 0
initialization: dp[0][0] = 1
int MOD = 1000000007;
public int numRollsToTarget(int d, int f, int target) {
int[][] dp = new int[d + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= d; i++) {
for (int j = 1; j <= target; j++) {
if (j > i * f) continue;
for (int k = 1; k <= f; k++) {
if (j < k) break;
dp[i][j] += dp[i - 1][j - k];
dp[i][j] = dp[i][j] % MOD;
}
}
}
return dp[d][target];
}dp[i][j]: how many ways to assign symbols to make sum of j nums equal to target i.
dp[i][j] = dp[i - nums[j]][j - 1] + dp[i + nums[j]][j - 1]
Since it includes the negative number and the total sum will not exceed 1000. Therefore the answer range is between -1000 and 1000. Shift everything to make it fit the matrix, which is 0 to 2001.
dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000]
dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000]
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
int[][] dp = new int[n][2001];
dp[0][nums[0] + 1000] = 1;
dp[0][-nums[0] + 1000] += 1;
for (int i = 1; i < n; i++) {
for (int sum = -1000; sum <= 1000; sum++) {
if (dp[i - 1][sum + 1000] > 0) {
dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
}
}
}
return S <= 1000 ? dp[n - 1][S + 1000] : 0;
}Check if the sum of all elements can be divided by 2, and array of numbers can sum up to sum / 2.
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]] if j - nums[i - 1] >= 0
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) return true;
int n = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) return false;
sum /= 2;
boolean[][] dp = new boolean[n + 1][sum + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];
if (j - nums[i - 1] >= 0) {
dp[i][j] |= dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}Dp:
dp[i]represents the LIS up to indexi.Init, fill
dparray with 1 since the LIS of a single element is 1.
T: O(n ^ 2) S: O(n)
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 0; i < nums.length; i++) {
int max = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
max = Math.max(max, dp[j]);
}
}
dp[i] = max + 1;
res = Math.max(max, res);
}
return res;
}DP: Binary Search T: O(nlogn) link
Solution1: for each number in the array, save it is difference and the longest arithmetic subsequence of that difference. T: O(n^2)
public int longestArithSeqLength(int[] A) {
if (A.length <= 1) return A.length;
int n = A.length;
Map<Integer, Integer>[] dp = new HashMap[n];
for (int i = 0; i < A.length; i++) {
dp[i] = new HashMap<Integer, Integer>();
}
int res = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int diff = A[i] - A[j];
int len = 2;
if (dp[j].containsKey(diff)) {
len = dp[j].get(diff) + 1;
}
dp[i].put(diff, len);
res = Math.max(res, len);
}
}
return res;
}Use relation: A[k] = 2 * A[j] - A[i] where i < j < k to find the k and save the index of k to an array: T: O(n^2)
public int longestArithSeqLength(int[] A) {
int n = A.length;
int[][] dp = new int[n][n];
int[] indices = new int[1001];
Arrays.fill(indices, -1);
int max = 2;
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], 2);
for (int j = i + 1; j < n; j++) {
int num = A[i] * 2 - A[j];
if (num >= 0 && indices[num] != -1) {
dp[i][j] = dp[indices[num]][i] + 1;
max = Math.max(max, dp[i][j]);
}
}
indices[A[i]] = i;
}
return max;
}Similar as two sum technique, search for arr[i] - diff in the hashmap and extend its length if there is a value.
public int longestSubsequence(int[] arr, int difference) {
Map<Integer, Integer> count = new HashMap<>();
int res = 1;
for (int i = 0; i < arr.length; i++) {
if (count.containsKey(arr[i] - difference)) {
count.put(arr[i], count.get(arr[i] - difference) + 1);
} else {
count.put(arr[i], 1);
}
res = Math.max(res, count.get(arr[i]));
}
return res;
}Use DP to calculate the probability to reach each grid on the next level. Then sums up the probabilities on all grids.
int[][] dirs = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2,1}, {-2,1}, {2,-1}, {-2,-1}};
public double knightProbability(int N, int K, int r, int c) {
double[][] dp = new double[N][N];
dp[r][c] = 1;
while (K-- > 0) {
double[][] dp2 = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int[] dir : dirs) {
int next_x = i + dir[0];
int next_y = j + dir[1];
if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < N) {
dp2[next_x][next_y] += dp[i][j] / 8.0;
}
}
}
}
dp = dp2;
}
double res = 0.0;
for (double[] row : dp) {
for (double d : row) {
res += d;
}
}
return res;
}Starts with all 10 numbers as 1, rolling save all combinations from the past and mod by modulo.
int[][] moves = new int[][]{ {4, 6}, {8, 6}, {7, 9}, {4, 8},
{3, 9, 0}, {}, {1, 7, 0},
{2, 6}, {1, 3}, {2, 4}};
public int knightDialer(int n) {
int MOD = 1000000007;
int[] dp = new int[10];
Arrays.fill(dp, 1);
while (--n > 0) {
int[] temp = new int[10];
for (int k = 0; k <= 9; k++) {
for (int next : moves[k]) {
temp[next] += dp[k];
temp[next] %= MOD;
}
}
dp = temp;
}
int res = 0;
for (int i = 0; i < 10; i++) {
res += dp[i];
res %= MOD;
}
return res;
}public int numTrees(int n) {
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}dp[i] = min = Math.min(dp[j] + (i / j), dp[i / j] + j)
public int minSteps(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
int min = i;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
min = Math.min(min,
Math.min(dp[j] + (i / j),
dp[i / j] + j));
}
}
dp[i] = min;
}
return dp[n];
}Initialize a map to store the current stone and the steps it can reach. Loop over the stones and create empty HashSets for all stones. Put <0, [1]> in the map to make sure that the frog move the first step.
Loop over the stones except the last one (i < stones.length - 1), get the next steps of the current stone, if stone + step reach the last stone (stone + step == stones[stones.length - 1]), return true.
Otherwise, add the k + 1, k , k - 1 step to map.get(stone + step), it indicates how many steps frog can move on the next stone.
public boolean canCross(int[] stones) {
Map<Integer, Set<Integer>> map = new HashMap<>();
map.put(0, new HashSet<>());
map.get(0).add(1);
for (int i = 1; i < stones.length; i++) {
map.put(stones[i], new HashSet<>());
}
for (int i = 0; i < stones.length - 1; i++) {
int stone = stones[i];
for (int step : map.get(stone)) {
if (stone + step == stones[stones.length - 1]) {
return true;
}
Set<Integer> nextset = map.get(stone + step);
if (nextset != null) {
nextset.add(step);
if (step - 1 > 0) nextset.add(step - 1);
nextset.add(step + 1);
}
}
}
return false;
} public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
for (int x : iNums) {
nums[n++] = x;
}
nums[0] = nums[n++] = 1;
int[][] dp = new int[n][n];
for (int k = 2; k < n; k++) {
for (int left = 0; left < n - k; left++) {
int right = left + k;
for (int i = left + 1; i < right; i++) {
dp[left][right]
= Math.max(dp[left][right],
nums[left] * nums[i] * nums[right]
+ dp[left][i] + dp[i][right]);
}
}
}
return dp[0][n - 1];
}public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length(), len2 = s2.length();
if(s3.length() != len1 + len2){
return false;
}
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for(int i = 1; i <= len1; i++){ //base case, go down
dp[i][0] = dp[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));
}
for(int i = 1; i <= len2; i++){ //base case, go right
dp[0][i] = dp[0][i - 1] && (s2.charAt(i - 1) == s3.charAt(i - 1));
}
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
//case 1, special case, up and left has the same character.
if(s1.charAt(i - 1) == s3.charAt(i + j - 1) && s2.charAt(j - 1) == s3.charAt(i + j - 1)){
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
//case2, normal case, only from left
}else if(s1.charAt(i - 1) == s3.charAt(i + j - 1)){
dp[i][j] = dp[i - 1][j];
//case3, normal case, only from up
}else if(s2.charAt(j - 1) == s3.charAt(i + j - 1)){
dp[i][j] = dp[i][j - 1];
}
/*pay attention, no other cases here,think of: s1 = abc, s2 = def, s3 = abcdef,
while dp[2][1] will be one of "abd,adb, bad, bda, dab, dba", and we try to match "abc" no match!
Think of this problem as a matrix, we are tring to find out if there is a path from [0,0] to [len1 - 1, len2 - 1],
so dp[i][j] == false, only mean dp[i][j] is not on the valid path, does not mean there is no such path exists!
a b c
☑️ ☑️ ☑️
d ☑️
e ☑️
f ☑️(valid path)
*/
}
}
return dp[len1][len2];
}public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int m = s.length(), n = p.length();
return helper(s, 0, p, 0, new boolean[m][n], new boolean[m][n]);
}
private boolean helper(String s, int i, String p, int j, boolean[][] visited, boolean[][] memo) {
if (j == p.length()) return i == s.length();
if (i == s.length()) return matchpattern(p, j);
if (visited[i][j]) return memo[i][j];
boolean match = false;
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
match = ((s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && helper(s, i + 1, p, j, visited, memo))
|| helper(s, i, p, j + 2, visited, memo);
} else if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
match = helper(s, i + 1, p, j + 1, visited, memo);
}
visited[i][j] = true;
memo[i][j] = match;
return match;
}
private boolean matchpattern(String p, int start) {
for (int i = start; i < p.length(); i += 2) {
if (i + 1 >= p.length() || p.charAt(i + 1) != '*') return false;
}
return true;
}public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] visited = new boolean[m][n];
boolean[][] memo = new boolean[m][n];
return helper(s, 0, p, 0, visited, memo);
}
private boolean helper(String s, int i, String p, int j, boolean[][] visited, boolean[][] memo) {
if (j == p.length()) {
return i == s.length();
}
if (i == s.length()) {
return allStar(p, j);
}
if (visited[i][j]) {
return memo[i][j];
}
boolean match = false;
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
match = helper(s, i + 1, p, j + 1, visited, memo);
} else if (p.charAt(j) == '*') { // "*" scenario
match = helper(s, i, p, j + 1, visited, memo) || helper(s, i + 1, p, j, visited, memo);
}
visited[i][j] = true;
memo[i][j] = match;
return match;
}
private boolean allStar(String p, int pIndex) {
for (int i = pIndex; i < p.length(); i++) {
if (p.charAt(i) != '*') {
return false;
}
}
return true;
}Card Game
Two players take turns to take cards in a row. Each player take from 1 to 3 cards. Compute the max of the first player gets.
public int stoneGameII(int[] piles) {
int[] presum = Arrays.copyOf(piles, piles.length);
int n = piles.length;
for (int i = presum.length - 2; i >= 0; i--) {
presum[i] += presum[i + 1];
}
return helper(presum, 0, 1, new int[n][n]);
}
private int helper(int[] presum, int startIndex, int M, int[][] memo) {
if (startIndex + 2 * M >= presum.length) {
return presum[startIndex];
}
if (memo[startIndex][M] > 0) return memo[startIndex][M];
int take = 0, res = 0;
for (int k = 1; k <= M * 2; k++) {
take = presum[startIndex] - presum[startIndex + k];
res = Math.max(res, take + presum[startIndex + k] - helper(presum, startIndex + k, Math.max(M, k), memo));
}
memo[startIndex][M] = res;
return res;
}3D dp. There are four scenarios: hori, verti, diag, adiag. For each scenario we need to maintain a 2D dp matrix so that it is a 3D dp.
public int longestLine(int[][] M) {
if (M == null || M.length == 0 || M[0].length == 0) return 0;
int m = M.length, n = M[0].length;
int[][][] dp = new int[m][n][4];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
for (int k = 0; k < 4; k++) {
dp[i][j][k] = 1;
}
if (i > 0 && dp[i - 1][j][0] != 0) {
dp[i][j][0] += dp[i - 1][j][0];
}
if (j > 0 && dp[i][j - 1][1] != 0) {
dp[i][j][1] += dp[i][j - 1][1];
}
if (i > 0 && j > 0 && dp[i - 1][j - 1][2] != 0) {
dp[i][j][2] += dp[i - 1][j - 1][2];
}
if (i > 0 && j < n - 1 && dp[i - 1][j + 1][3] != 0) {
dp[i][j][3] += dp[i - 1][j + 1][3];
}
for (int k = 0; k < 4; k++) {
res = Math.max(res, dp[i][j][k]);
}
}
}
}
return res;
}This is a tricky question. It asks if jump odd step, with the smallest number above current. If jump even step, with the largest number above current. This can be achieve by using TreeMap. Here are the rules:
During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that
A[i] <= A[j]and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that
A[i] >= A[j]and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
Loop over the array from end. This is due to we can reversely determine the start step from the end step. Initialize two boolean arrays to determine if it can reach by odd jumps or even jumps. Put the number and its index to the TreeMap.
public int oddEvenJumps(int[] A) {
int n = A.length;
boolean[] hi = new boolean[n]; //
boolean[] lo = new boolean[n]; //
hi[n - 1] = true;
lo[n - 1] = true;
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(A[n - 1], n - 1);
int count = 1;
for (int i = n - 2; i >= 0; i--) {
Integer floor = map.floorKey(A[i]);
Integer ceiling = map.ceilingKey(A[i]);
if (floor != null) { // even
hi[i] = lo[map.get(floor)];
}
if (ceiling != null) { // odd
lo[i] = hi[map.get(ceiling)];
}
map.put(A[i], i);
if (lo[i]) count++;
}
return count;
}Walk twice from (0,0) to (m - 1, n - 1) which gives the same result from walk over and walk back. DFS will TLE
public int cherryPickup(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int res = helper(grid, 0, 0, true);
return Math.max(res, 0);
}
private int helper(int[][] grid, int x, int y, boolean round1) {
if (x >= grid.length || y >= grid[0].length || grid[x][y] == -1) {
return Integer.MIN_VALUE;
}
int temp = grid[x][y];
grid[x][y] = 0;
int res;
if (x == grid.length - 1 && y == grid[0].length - 1) {
res = round1 ? helper(grid, 0, 0, false) : 0;
} else {
int right = helper(grid, x, y + 1, round1);
int down = helper(grid, x + 1, y, round1);
res = Math.max(right, down);
}
grid[x][y] = temp;
return res + temp;
}public int cherryPickup(int[][] grid) {
int N = grid.length, M = (N << 1) - 1;
int[][] dp = new int[N][N];
dp[0][0] = grid[0][0];
for (int n = 1; n < M; n++) {
for (int i = N - 1; i >= 0; i--) {
for (int p = N - 1; p >= 0; p--) {
int j = n - i, q = n - p;
if (j < 0 || j >= N || q < 0 || q >= N || grid[i][j] < 0 || grid[p][q] < 0) {
dp[i][p] = -1;
continue;
}
if (i > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p]);
if (p > 0) dp[i][p] = Math.max(dp[i][p], dp[i][p - 1]);
if (i > 0 && p > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p - 1]);
if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0);
}
}
}
return Math.max(dp[N - 1][N - 1], 0);
}Walk two robots simultaneously. First has 3 steps: left down, down, right down. Same thing for the 2nd one.
DFS + MEMO: TLE
public int cherryPickup(int[][] grid) {
int m = grid.length, n = grid[0].length;
Integer[][][] dp = new Integer[m][n][n];
return dfs(grid, m, n, 0, 0, n - 1, dp);
}
private int dfs(int[][] grid, int m, int n, int r, int c1, int c2, Integer[][][] dp) {
if (r == m) return 0;
if (dp[r][c1][c2] != null) return dp[r][c1][c2];
int res = 0;
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
int nc1 = c1 + i, nc2 = c2 + j;
if (nc1 >= 0 && nc1 < n && nc2 >= 0 && nc2 < n) {
res = Math.max(res, dfs(grid, m, n, r + 1, nc1, nc2, dp));
}
}
}
if (c1 == c2) {
res += grid[r][c1];
} else {
res += grid[r][c1] + grid[r][c2];
}
return res;
}DP
public int cherryPickup(int[][] grid) {
int m = grid.length, n = grid[0].length;
// dp[r][c1][c2]: starting from row r, column c1 and c2, max # of cherries.
int[][][] dp = new int[m][n][n];
for(int r = m - 1; r >= 0; r--) {
for(int c1 = 0; c1 < n; c1++) {
for(int c2 = 0; c2 < n; c2++) {
int val = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2];
if(r == m - 1) {
dp[r][c1][c2] = val;
continue;
}
int next = 0;
for(int i = -1; i <= 1; i++) {
for(int j = -1; j <= 1; j++) {
int c1_n = c1 + i, c2_n = c2 + j;
if(c1_n >= 0 && c1_n < n && c2_n >= 0 && c2_n < n) {
next = Math.max(next, dp[r + 1][c1_n][c2_n]);
}
}
}
dp[r][c1][c2] = val + next;
}
}
}
return dp[0][0][n - 1];
}class Solution {
public long maxCoins(int[] lane1, int[] lane2) {
int n = lane1.length;
// dp[pos][lane][switchesLeft]: max coins at position `pos`, in `lane` (0 or 1), with `switchesLeft` switches remaining
long[][][] dp = new long[n][2][3];
// Initialization at position 0
dp[0][0][2] = lane1[0]; // Start on lane 0 with 2 switches remaining
dp[0][0][0] = lane1[0]; // Special case: no switches allowed at all
dp[0][1][1] = lane2[0]; // Start on lane 1 with 1 switch remaining
long maxCoins = Math.max(dp[0][0][2], dp[0][1][1]);
for (int pos = 1; pos < n; pos++) {
// lane 0, 0 switches left:
// - Stay on lane 0 from previous step with 0 switches
// - Or switch from lane 1 using the last switch
dp[pos][0][0] = Math.max(dp[pos - 1][0][0], dp[pos - 1][1][1]) + lane1[pos];
// lane 0, 2 switches left:
// - Continue on lane 0 without switching
// - Or reset here (if this is the first move)
dp[pos][0][2] = Math.max(dp[pos - 1][0][2] + lane1[pos], lane1[pos]);
// lane 1, 1 switch left:
// - Stay on lane 1 with 1 switch left
// - Or switch from lane 0 with 2 switches left
// - Or start from here
dp[pos][1][1] = Math.max(Math.max(dp[pos - 1][1][1], dp[pos - 1][0][2]), 0) + lane2[pos];
// Track best result so far
long currentMax = Math.max(Math.max(dp[pos][0][0], dp[pos][0][2]), dp[pos][1][1]);
maxCoins = Math.max(maxCoins, currentMax);
}
return maxCoins;
}
}
3610. Minimum Number of Primes to Sum to Target
class Solution {
int min = Integer.MAX_VALUE;
public int minNumberOfPrimes(int n, int m) {
List<Integer> primes = getFirstNPrimes(m);
// DP approach - similar to coin change problem
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int min = dp[i];
for (int prime : primes) {
if (prime > i) break;
if (dp[i - prime] == Integer.MAX_VALUE) continue;
min = Math.min(min, dp[i - prime] + 1);
}
dp[i] = min;
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}
/**
* Returns the first n prime numbers using Sieve of Eratosthenes with upper bound estimation
* @param n the number of primes to find
* @return List of the first n prime numbers
*/
public static List<Integer> getFirstNPrimes(int n) {
if (n <= 0) {
throw new IllegalArgumentException("n must be positive");
}
// Handle small cases directly
List<Integer> primes = new ArrayList<>();
if (n >= 1) primes.add(2);
if (n >= 2) primes.add(3);
if (n >= 3) primes.add(5);
if (n >= 4) primes.add(7);
if (n >= 5) primes.add(11);
if (n >= 6) primes.add(13);
if (n <= 6) {
return primes.subList(0, n);
}
// Estimate upper bound using prime number theorem approximation
int upperBound = estimateUpperBound(n);
// Keep expanding the bound until we find enough primes
while (true) {
// Create sieve array
boolean[] isPrime = new boolean[upperBound + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
// Sieve of Eratosthenes
for (int i = 2; i * i <= upperBound; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= upperBound; j += i) {
isPrime[j] = false;
}
}
}
// Collect primes into list
List<Integer> foundPrimes = new ArrayList<>();
for (int i = 2; i <= upperBound && foundPrimes.size() < n; i++) {
if (isPrime[i]) {
foundPrimes.add(i);
}
}
// Return first n primes if we found enough
if (foundPrimes.size() >= n) {
return foundPrimes.subList(0, n);
}
// If we didn't find enough primes, double the upper bound
upperBound *= 2;
}
}
/**
* Estimates upper bound for the nth prime using prime number theorem
* Formula: p_n ≈ n * ln(n) + n * ln(ln(n)) for n >= 6
*/
private static int estimateUpperBound(int n) {
if (n < 6) return 15;
double logN = Math.log(n);
double logLogN = Math.log(logN);
// Using refined approximation with safety factor
double estimate = n * (logN + logLogN - 1 + (logLogN - 2) / logN);
// Add safety factor to ensure we don't underestimate
return (int) Math.ceil(estimate * 1.1);
}
}Last updated
Was this helpful?