Dynamic programming in O(M*N) , solution in C++.


  • 12
    L
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            int P[101][101];
            P[1][1]=1;
            for (int i=2; i<=n; i++)
            {
                P[1][i]=1;
            }
            for (int i=2; i<=m; i++)
            {
                P[i][1]=1;
            }
            for (int i=2; i<=m; i++)
            {
                for (int j=2; j<=n; j++)
                {
                    P[i][j]=P[i-1][j]+P[i][j-1];
                }
            }
            return P[m][n];
        }
    };

Log in to reply
 

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