[DP] Share my C++ 7 lines 0ms solution with explanation

  • 0

    Notice that the robot can only go down or right, so the total path=robot go down at starting point + robot go right at starting point; if robot go down, m=m-1, if go right, n=n-1, so it's a typical dynamic programming problem:

        int uniquePaths(int m, int n) {
            for(int i=0;i<m+1;i++) dp[i][1]=1;
            for(int i=0;i<n+1;i++) dp[1][i]=1;
            for(int i=2;i<m+1;i++)
                for(int j=2;j<n+1;j++)
            return dp[m][n];

    NOTE: Recursion version will get TLE and won't pass...

        int uniquePaths(int m, int n) {
            if(m==1||n==1) return 1;
            return uniquePaths(m,n-1)+uniquePaths(m-1,n);

Log in to reply

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