DSA Notes

2D DP

Note :- Memoziation and Tabulation are always traversed in opposite direction, and when we space optimize there we reduce one dimension less.

Ninja Training(striver)

class Solution {
public:
    int ninjaTraining(vector<vector<int>>& points) {
        int n = points.size();
        vector<vector<int>> dp(n, vector<int>(4,-1)); // 4 choices to pick
        return f(n-1, 3, points, dp);
    }
    int f(int day, int last, vector<vector<int>>& points, vector<vector<int>>& dp){
        if (dp[day][last] != -1) return dp[day][last];
        if (day == 0){
            int maxi = 0;
            for (int i = 0; i <= 2; i++) {
                if (i != last) maxi = max(maxi, points[0][i]);
            }
            return dp[day][last] = maxi;   
        }
        int maxi = 0;
        for (int i = 0; i <=2; i++){
            if (i != last){
                int activity = points[day][i] + f(day-1, i, points, dp);
                maxi = max(maxi, activity);
            }
        }
        return dp[day][last] = maxi;
    }
};

Unique paths in Grids(from top-left to bottom-right)

// f(i, j) recursive function means from (0,0) to (i,j)
class Solution {
public:
    // top-down memoziation
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, -1));
        // initially at bottom-right
        return gridpaths(m-1, n-1, dp);
    }
    int gridpaths(int i, int j, vector<vector<int>> &dp){
        if (i == 0 && j == 0) return 1;
        if (i < 0 || j < 0) return 0; // out of bounds
        if (dp[i][j] != -1) return dp[i][j];
        int up = gridpaths(i-1, j, dp);
        int left = gridpaths(i, j-1, dp);
        return dp[i][j] = up + left;
    }
};
// to reduce stack space, we can use tabulation

• If there is an obstacle (value 1) in the obstaclegrid given, we cannot pass through it.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1));
        return gridpaths(m-1, n-1, obstacleGrid, dp);
    }
    int gridpaths(int i, int j, vector<vector<int>>& obstacleGrid, vector<vector<int>> &dp){
        if (i < 0 || j < 0) return 0; // out of bounds
        if (obstacleGrid[i][j] == 1) return 0;
        if (i == 0 && j == 0) return 1;
        if (dp[i][j] != -1) return dp[i][j];
        int up = gridpaths(i-1, j, obstacleGrid, dp);
        int left = gridpaths(i, j-1, obstacleGrid, dp);
        return dp[i][j] = up + left;
    }        
};

Minimum cost path in grid from top-left to bottom-right (only down and right directions move)

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1));
        return mindp(m-1, n-1, grid, dp);
    }
    int mindp(int i, int j, vector<vector<int>>& grid, vector<vector<int>> &dp){
        if (i == 0 && j == 0) return grid[0][0];
        if (i < 0 || j < 0) return 1e9; // out of bounds
        if (dp[i][j] != -1) return dp[i][j];
        int upsum = grid[i][j] + mindp(i-1, j, grid, dp);
        int leftsum = grid[i][j] + mindp(i, j-1, grid, dp);
        return dp[i][j] = min(upsum, leftsum);
    }
};

Minimum path sum in triangle from top to bottom

// Memoziation(0 -> n-1)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp(n);
        for (int i = 0; i < n; i++) dp[i] = vector<int>(i + 1, -1);
        return minpathsum(0, 0, n, triangle, dp);
    }
    int minpathsum(int i, int j, int n, vector<vector<int>>& triangle, vector<vector<int>>& dp){
        if (i == n-1) return triangle[n-1][j];
        if (dp[i][j] != -1) return dp[i][j];
        int down = triangle[i][j] + minpathsum(i+1, j, n, triangle, dp);
        int diagonal = triangle[i][j] + minpathsum(i+1, j+1, n, triangle, dp);
        return dp[i][j] = min(down, diagonal);
    }
};


// Tabulation(n-1 -> 0)
int minimumTotal(vector<vector<int> > &triangle) {
    int n = triangle.size();
    vector<vector<int> > dp(n, vector<int>(n, -1));
    // Initialize the bottom row of dp with the values from the triangle
    for (int j = 0; j < n; j++) {
        dp[n - 1][j] = triangle[n - 1][j];
    }

    // Iterate through the triangle rows in reverse order
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i; j >= 0; j--) {
            int down = triangle[i][j] + dp[i + 1][j];
            int diagonal = triangle[i][j] + dp[i + 1][j + 1];
            dp[i][j] = min(down, diagonal);
        }
    }

    // The top-left cell of dp now contains the minimum path sum
    return dp[0][0];
}

Max Falling Path sum (maximum path sum from any cell of the first row to any cell of the last row)

// memoization
class Solution {
public:
    int maxFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        int maxi = INT_MIN;
        for (int j = 0; j < m; j++){
            int pathsum = pathdp(n-1, j, m, matrix, dp);
            maxi = max(maxi, pathsum);
        }
        return maxi;
    }
    int pathdp(int i, int j, int m, vector<vector<int>>& matrix, vector<vector<int>>& dp){
        if (j < 0 || j > m-1) return -1e9;
        if (i == 0) return matrix[0][j];
        if (dp[i][j] != -1) return dp[i][j];
        int up = matrix[i][j] + pathdp(i-1, j, m, matrix, dp);
        int upleft = matrix[i][j] + pathdp(i-1, j-1, m, matrix, dp);
        int upright = matrix[i][j] + pathdp(i-1, j+1, m, matrix, dp);
        return dp[i][j] = max(up, max(upleft, upright));
    }
};


// Tabulation
int getMaxPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));

    // BASE
    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 leftDia = matrix[i][j];
            if (j - 1 >= 0) {
                leftDia += dp[i - 1][j - 1];
            } else {
                leftDia += -1e9;
            }

            int rightDia = matrix[i][j];
            if (j + 1 < m) {
                rightDia += dp[i - 1][j + 1];
            } else {
                rightDia += -1e9;
            }
            dp[i][j] = max(up, max(leftDia, rightDia));
        }
    }

    // Find the maximum value in the last row of dp, which represents the maximum path sums ending at each cell
    int maxi = INT_MIN;
    for (int j = 0; j < m; j++) {
        maxi = max(maxi, dp[n - 1][j]);
    }
    return maxi;
}

3D DP - Alice and friends (striver) - Two starting points

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

    if (j1 < 0 || j1 > m-1 || j2 < 0 || j2 > m-1) return -1e9; // out of bounds

    // Destination Base case: If we are at the last row, return the chocolate at the positions (j1, j2)
    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;
    
    // Try all possible moves (up, left, right) for both positions (j1, j2)
    for (int d1 = -1; d1 <= 1; d1++) {
        for (int d2 = -1; d2 <= 1; d2++) {
            int ans;
            if (j1 == j2) ans = grid[i][j1] + maxdp(i + 1, j1 + d1, j2 + d2, n, m, grid, dp);
            else ans = grid[i][j1] + grid[i][j2] + maxdp(i + 1, j1 + d1, j2 + d2, n, m, grid, dp);

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

int maximumChocolates(int n, int m, vector<vector<int>> &grid) {
    // Create a 3D DP array to store computed results
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(m, -1)));

    return maxdp(0, 0, m - 1, n, m, grid, dp);
}

Count square submatrices with all ones

• here recursion is not intuitive, we use tabulation
• dp array, dp[i][j] will signify, how many squares end at the cell (i, j) i.e. for how many squares the rightmost bottom cell is (i, j).

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));

        for (int i = 0; i < n; i++) dp[i][0] = matrix[i][0];
        for (int j = 0; j < m; j++) dp[0][j] = matrix[0][j];

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == 1) dp[i][j] = 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
                else dp[i][j] = 0;
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count += dp[i][j];
            }
        }
        return count;
    }
};