Java Solution with DP


  • 0
    Y

    If target is in the first row or first column, only one path. Otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1], first item is moving down and second item is moving right.

    class Solution {
        public int uniquePaths(int m, int n) {
            
            int[][] dp = new int[m][n];
            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
            return dp[m-1][n-1];
            
        }
    }
    

Log in to reply
 

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