Skip to content

3-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 3 variable, its a 3D 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.

Chocolates Pickup

Steps to form the recursive solution :-

Base Case:

  • If j1<0 or j1>=M or j2<0 or j2>=M , then we return -1e9

  • When i == N-1, it means we are at the last row, so we need to return from here. Now it can happen that at the last row, both Alice and Bob are at the same cell, in this condition we will return only chocolates collected by Alice, mat[i][j1] ( as question states that the chocolates cannot be doubly calculated), otherwise we return sum of chocolates collected by both, mat[i][j1] + mat[i][j1][j2].

if(j1 < 0 || j1 >= m || j2 >= m || j2 < 0){
    return -1e9;
}
if(i == n-1){
    if(j1 == j2){
        return grid[i][j1];
    }
    else{
        return grid[i][j1] + grid[i][j2];
    }
}

Step 2: Try out all possible choices at a given index.

  • we need to understand that we want to move Alice and Bob together. Both of them can individually move three moves but say Alice moves to bottom-left, then Bob can have three different moves for Alice’s move, and so on.

  • Hence we have a total of 9 different options at every f(i,j1,j2) to move Alice and Bob. Now we can manually write these 9 options or we can observe a pattern in them, first Alice moves to one side and Bob tries all three choices, then again Alice moves, then Bob, and so on. This pattern can be easily captured by using two nested loops that change the column numbers(j1 and j2).

  • Note: if (j1===j2), as discussed in the base case, we will only consider chocolates collected by one of them otherwise we will consider chocolates collected by both of them.

Step 3: Take the maximum of all choices

int maxi = INT_MIN;
for(int p = -1 ; p <= 1 ; p++){
    for(int q = -1 ; q <= 1 ; q++){
        int ans;

        if(j1 == j2){
            ans = grid[i][j1];
        }
        else{
            ans = grid[i][j1]+ grid[i][j2];
        }
        ans += solver(i+1 , j1+p , j2+q , n , m , grid , dp);

        maxi = max(maxi , ans);
    }
}

memoization

class Solution{
  public:

    int solver(int i , int j1 , int j2 , int n , int m , vector<vector<int>> &grid , vector<vector<vector<int>>> &dp){

        if(j1 < 0 || j1 >= m || j2 >= m || j2 < 0){
            return -1e9;
        }
        if(i == n-1){
            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 maxi = INT_MIN;
        for(int p = -1 ; p <= 1 ; p++){
            for(int q = -1 ; q <= 1 ; q++){
                int ans;

                if(j1 == j2){
                    ans = grid[i][j1];
                }
                else{
                    ans = grid[i][j1]+ grid[i][j2];
                }
                ans += solver(i+1 , j1+p , j2+q , n , m , grid , dp);

                maxi = max(maxi , ans);
            }
        }
        return dp[i][j1][j2] = maxi;
    }

    int solve(int n, int m, vector<vector<int>>& grid) {

        vector<vector<vector<int>>> dp(n , vector<vector<int>>(m , vector<int>(m , -1)));
        return solver(0 , 0 , m-1 , n , m , grid , dp);
    }
};

tabulation

💯 🔥 🚀