2-D Dynamic Programming
We defined sub-problems and their dependency, other important entities in dp are the dependent elements or variables. The count of these variables defines the dimension of the problem. If a problem is dependent on 2 variable, its a 2D dp problem.
🧠 👍 Out of bound base cases should be written at the top of all of the base cases.
Questions
💡 In the below questions try to draw the recursion's diagram of each problem on the 📝 paper.
Geek's Training
🤞 For this question : - Only think about which activity is done before and you should pass that activity to recursion that's why the same activity will not happen next day.
memoization
int solver(vector<vector<int>> &points , int n , int last_task , vector<vector<int>> &dp){
if(n == 0){
int maxi = INT_MIN;
for(int i = 0 ; i < 3 ; i++){
if(i != last_task){
maxi = max(maxi , points[n][i]);
}
}
return maxi;
}
if(dp[n][last_task] != -1){
return dp[n][last_task];
}
int max_points = INT_MIN;
for(int i = 0 ; i < 3 ; i++){
if(i != last_task){
int point = points[n][i] + solver(points , n-1 , i , dp);
max_points = max(max_points , point);
}
}
return dp[n][last_task] = max_points;
}
tabulation
int tabulation(vector<vector<int>> &points , int n){
vector<vector<int>> dp(n , vector<int> (4,-1));
dp[0][0] = max(points[0][1], points[0][2]);
dp[0][1] = max(points[0][0], points[0][2]);
dp[0][2] = max(points[0][0], points[0][1]);
dp[0][3] = max(points[0][0], max(points[0][1], points[0][2]));
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < 4 ; j++){
for (int task = 0; task <= 2; task++) {
if (task != j) {
int activity = points[i][task] + dp[i - 1][task];
dp[i][j] = max(dp[i][j], activity);
}
}
}
}
return dp[n-1][3];
}
Grid Unique Paths
memoization
int solver(int m , int n , vector<vector<int>> &dp){
if(m < 0 || n < 0){
return 0;
}
if(m == 0 && n == 0){
return 1;
}
if(dp[m][n] != -1){
return dp[m][n];
}
int up = solver(m-1 , n , dp);
int left = solver(m , n-1 , dp);
return dp[m][n] = up+left;
}
tabulation
int tabulation(int m , int n){
vector<vector<int>> dp(m+1 , vector<int> (n , -1));
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(i == 0 && j == 0){
dp[i][j] = 1;
continue;
}
int down = 0;
int right = 0;
if(i > 0)
down = dp[i-1][j];
if(j > 0)
right = dp[i][j-1];
dp[i][j] = down+right;
}
}
return dp[m-1][n-1];
}
Grid Unique Paths II
memoization
int solver(vector<vector<int>> &obstacleGrid , int m , int n , vector<vector<int>> &dp){
if(m >= 0 && n >= 0 && obstacleGrid[m][n] == 1){
return 0;
}
if(m < 0 || n < 0){
return 0;
}
if(m == 0 && n == 0){
return 1;
}
if(dp[m][n] != -1){
return dp[m][n];
}
int up = solver(obstacleGrid , m-1 , n , dp);
int left = solver(obstacleGrid , m , n-1 , dp);
return dp[m][n] = up+left;
}
tabulation
int tabulation(vector<vector<int>> &obstacleGrid , int m , int n){
vector<vector<int>> dp(m , vector<int> (n , -1));
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(i >= 0 && j >= 0 && obstacleGrid[i][j] == 1){
dp[i][j] = 0;
continue;
}
if(i == 0 && j == 0){
dp[i][j] = 1;
continue;
}
int down = 0;
int right = 0;
if(i > 0)
down = dp[i-1][j];
if(j > 0)
right = dp[i][j-1];
dp[i][j] = down+right;
}
}
return dp[m-1][n-1];
}
Minimum path sum
memoization
int solver(vector<vector<int>> &grid , int n , int m , vector<vector<int>> &dp){
if(n < 0 || m < 0){
return 1e8;
}
if(n == 0 && m == 0){
return grid[n][m];
}
if(dp[n][m] != -1){
return dp[n][m];
}
int up = grid[n][m] + solver(grid , n-1 , m , dp);
int left = grid[n][m] + solver(grid , n , m-1 , dp);
return dp[n][m] = min(up , left);
}
tabulation
int tabulation(vector<vector<int>> &grid , int n , int m){
vector<vector<int>> dp(n , vector<int> (m , -1));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(i == 0 && j == 0){
dp[i][j] = grid[0][0];
continue;
}
int down = grid[i][j];
if(i > 0)
down += dp[i-1][j];
else
down += 1e8;
int right = grid[i][j];
if(j > 0)
right += dp[i][j-1];
else
right += 1e8;
dp[i][j] = min(down , right);
}
}
return dp[n-1][m-1];
}
Minimum path sum in triangle
memoization
int solver(vector<vector<int>> &triangle , int i , int j , int n , vector<vector<int>> &dp){
if(i == n){
return triangle[i][j];
}
if(dp[i][j] != -1){
return dp[i][j];
}
int down = triangle[i][j] + solver(triangle , i+1 , j , n , dp);
int diag = triangle[i][j] + solver(triangle , i+1 , j+1 , n , dp);
return dp[i][j] = min(down , diag);
}
tabulation
int tabulation(vector<vector<int>> &triangle , int n){
vector<vector<int>> dp(n , vector<int> (n , -1));
for(int i = 0 ; i < n ; i++){
dp[n-1][i] = triangle[n-1][i];
}
for(int i = n-2 ; i >= 0 ; i--){
for(int j = i ; j >= 0 ; j--){
int up = triangle[i][j] + dp[i+1][j];
int diag = triangle[i][j] + dp[i+1][j+1];
dp[i][j] = min(up , diag);
}
}
return dp[0][0];
}
Minimum Falling Path Sum
memoization
int solver(int i , int j , int m , vector<vector<int>> &matrix , vector<vector<int>> &dp){
if(i < 0 || j < 0 || j >= m){
return 1e8;
}
if(i == 0){
return matrix[0][j];
}
if(dp[i][j] != -1){
return dp[i][j];
}
int up = matrix[i][j] + solver(i-1 , j , m , matrix , dp);
int diag_left = matrix[i][j] + solver(i-1 , j-1 , m , matrix , dp);
int diag_right = matrix[i][j] + solver(i-1 , j+1 , m , matrix , dp);
return dp[i][j] = min(up , min(diag_left , diag_right));
}
tabulation
int tabulation(int n , int m , vector<vector<int>> &matrix){
vector<vector<int>> dp(n , vector<int> (m , -1));
for (int j = 0; j < m; j++) {
dp[0][j] = matrix[0][j];
}
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
int up = matrix[i][j] + dp[i-1][j];
int diag_left = matrix[i][j];
if (j-1 >= 0) {
diag_left += dp[i-1][j-1];
} else {
diag_left += 1e9;
}
int diag_right = matrix[i][j];
if (j+1 < m) {
diag_right += dp[i-1][j+1];
} else {
diag_right += 1e9;
}
dp[i][j] = min(up , min(diag_left , diag_right));
}
}
int mini = INT_MAX;
for (int j = 0; j < m; j++) {
mini = min(mini, dp[n - 1][j]);
}
return mini;
}
💯 🔥 🚀