Dp Learnings (27 Part Series)
1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score
You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.
You have two robots that can collect cherries for you:
- Robot #1 is located at the top-left corner (0, 0), and
- Robot #2 is located at the top-right corner (0, cols – 1).
Return the maximum number of cherries collection using both robots by following the rules below:
- From a cell (i, j), robots can move to cell (i + 1, j – 1), (i + 1, j), or (i + 1, j + 1).
- When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
- When both robots stay in the same cell, only one takes the cherries.
- Both robots cannot move outside of the grid at any moment.
- Both robots should reach the bottom row in grid.
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.
class Solution {
// we will use 3dp for optimizing this problem
public int cherryPickup(int[][] grid) {
// since both the robots are moving simultaneously hence they will
// be at the same row all the time.
// hence only one row index is needed .
// j1 is for robot1 and j2 is for robot2
int dp[][][] = new int[grid.length][grid[0].length][grid[0].length];
for(int i =0;i<dp.length;i++){
for(int matrix[] : dp[i]){
Arrays.fill(matrix,-1);
}
}
return solve(grid,0,0,grid[0].length-1,dp);
}
public int solve(int[][] grid, int i,int j1,int j2,int [][][] dp){
if(j1<0 || j2<0 || j1>=grid[0].length || j2 >= grid[0].length) return 0;
if(i == grid.length-1) {
// here are two cases , either both robot1 and robot2 have arrived at the same cell in the last row or different cells in the last row
if(j1==j2) return grid[i][j1];
else return grid[i][j1] + grid[i][j2];
}
if(dp[i][j1][j2]!=-1) return dp[i][j1][j2];
int maximum = 0;
/* for every move of robot1 robot2 has the chance to move either rightdiagonal or down or left diagonal hence the below code will run for 9 times 3*3 */
for(int a = j1-1;a<=j1+1;a++){
for(int b = j2-1;b<=j2+1;b++){
if(j1==j2) { // since j1 and j2 are same that means robot1 and robot2 are at the same cell . Hence take current cell value + solve() again we can take index j1 or j2 any one as the value at the cell is same
maximum =Integer.max(maximum,grid[i][j1]+solve(grid,i+1,a,b,dp));
}
else {
maximum =Integer.max(maximum, grid[i][j1]+grid[i][j2] + solve(grid,i+1,a,b,dp));
}
}
}
return dp[i][j1][j2] = maximum;
}
}
Enter fullscreen mode Exit fullscreen mode
Dp Learnings (27 Part Series)
1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score
暂无评论内容