Generic Idea for board movement problems. Java Solution.


  • 1
    S

    All these "Move from top left to bottom right by only moving rightward or downward" problems can be solved using the same DP idea which can be extended to multiple problems.

    Start from the end point (bottom right) and work backward (top left).

    Here's a solution to "Unique Paths".
    https://leetcode.com/problems/unique-paths/

            for(int i = m - 1; i >= 0; i--)
            {
                for(int j = n - 1; j >= 0; j--)
                {
                    if(i == m-1 && j != n-1)
                    {
                        dp[i][j] = dp[i][j+1];
                    }
                    else if( i != m-1 && j == n-1)
                    {
                        dp[i][j] = dp[i+1][j];
                    }
                    else if(i != m-1 && j != n-1)
                    {
                        dp[i][j] = dp[i+1][j] + dp[i][j+1];
                    }
                }
            }
            
            return dp[0][0];
    

    Here's a solution to "Minimum Path Sum" which is very similar:
    https://leetcode.com/problems/minimum-path-sum/

            for(int i = rows - 1; i >= 0; i--)
            {
                for(int j = cols - 1; j >= 0; j--)
                {
                    if(i == rows-1 && j != cols-1)
                    {
                        dp[i][j] = grid[i][j] + dp[i][j+1];
                    }
                    
                    else if(i != rows-1 && j == cols-1)
                    {
                        dp[i][j] = grid[i][j] + dp[i+1][j];
                    }
                    
                    else if(i != rows-1 && j != cols-1)
                    {
                        dp[i][j] = grid[i][j] + Math.min(dp[i][j+1], dp[i+1][j]);
                    }
                    
                    else
                    {
                        dp[i][j] = grid[i][j];
                    }
                }
            }
            
            return dp[0][0];
    

    This method can be extended to the "Dungeon Game" as well:

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            
            int m = dungeon.length;
            int n = dungeon[0].length;
            
            int[][] dp = new int[m][n];
            
            for(int i = m - 1; i >= 0; i--)
            {
                for(int j = n - 1; j >= 0; j--)
                {
                    if(i == m-1 && j != n-1)
                    {
                        dp[i][j] = Math.max(1, dp[i][j+1] - dungeon[i][j]);
                    }
                    else if(i != m-1 && j == n-1)
                    {
                        dp[i][j] = Math.max(1, dp[i+1][j] - dungeon[i][j]);
                    }
                    else if(i != m-1 && j != n-1)
                    {
                        dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);
                    }
                    else
                    {
                        dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                    }
                }
            }
            
            return dp[0][0];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.