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 climbStairs(int n) {
int[] dp = new int[n + 1];
int one = 1;
int two = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
one = one + two;
} else {
two = one + two;
}
}
return n % 2 == 0 ? one : two;
}
int[] dp;
public int climbStairs(int n) {
dp = new int[n + 1];
return dfs(n);
}
private int dfs(int n) {
if (n <= 1) return 1;
if (dp[n] != 0) return dp[n];
int res = dfs(n - 2) + dfs(n - 1);
dp[n] = res;
return res;
}
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
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];
}
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
int[] newRow = new int[n];
for (int j = 0; j < n; j++) {
if (j == 0) {
newRow[j] = 1;
} else {
newRow[j] = dp[j] + newRow[j - 1];
}
}
dp = newRow;
}
return dp[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]);
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];
}
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
int nottakelast = nums[0];
int takelast = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int temp = Math.max(nottakelast + nums[i], takelast);
nottakelast = takelast;
takelast = temp;
}
return Math.max(nottakelast, takelast);
}
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 maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != '1') {
continue;
}
int top = i > 0 ? dp[i-1][j] + 1: 1;
int left = j > 0 ? dp[i][j - 1] + 1: 1;
int lefttop = i > 0 && j > 0 ? dp[i-1][j- 1] + 1 : 1;
dp[i][j] = Math.min(Math.min(top, left), lefttop);
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;
}
public int maxSubArray(int[] nums) {
int n = nums.length;
int curt = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
curt = Math.max(curt + nums[i], nums[i]);
max = Math.max(max, curt);
}
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];
}
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];
}
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.
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.
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 index i.
Init, fill dp array 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;
}
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) {
if (s == null || p == null) return false;
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return dp[s.length()][p.length()];
}
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;
}
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
} else break;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][ j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
}
}
}
return dp[m][n];
}
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];
}