[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:
    dp[m][n]=dp[m][n-1]+dp[m-1][n];
    dp[1][1...n]=1;
    dp[1...m][1]=1;

        int uniquePaths(int m, int n) {
            //dp[m][n]=dp[m][n-1]+dp[m-1][n];
            vector<vector<int>>dp(m+1,vector<int>(n+1,0));
            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++)
                    dp[i][j]=dp[i][j-1]+dp[i-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.