Unique Paths

https://leetcode.com/problems/unique-paths/

递归问题转换成动态规划问题。每个问题可以分解成p[m][n]=p[m-1][n]+p[m][n-1]

动态规划：做一个动态二维数组，用于存放每步的解。最终的循环就是矩阵的所有点遍历一遍。

时间复杂度为m*n的矩阵遍历。

 1 class Solution {
 2 public:
 3     int uniquePaths(int m, int n) {
 4         int ** p;
 5         p=new int *[m+1];
 6         for(int i=1;i<m+1;i++)
 7             p[i]=new int[n+1];
 8         
 9         for(int i=1;i<=m;i++)
10         {
11             for(int j=1;j<=n;j++)
12             {
13                 if(i==1||j==1)
14                     p[i][j]=1;
15                 else
16                     p[i][j]=p[i-1][j]+p[i][j-1];
17             }
18         }
19         return p[m][n];
20         
21     }
22 };