Unique Paths I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/unique-paths/

题目：
A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?
Solution:
Dynamic programming. UP(i,j) = UP(i-1,j) + UP(i,j-1).

代码：

 class Solution {  
 public:  
   int uniquePaths(int m, int n) {  
     int dp[m][n];  
     for (int i = 0; i < m; i++) {  
       dp[i][0] = 1;  
     }    
     for (int j = 0; j < n; j++) {  
       dp[0][j] = 1;  
     }    
     for (int i = 1; i < m; i++) {  
       for (int j = 1; j < n; j++) {  
         dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
       }  
     }  
     return dp[m - 1][n - 1];  
   }  
 };  
   
 class Solution {  
 public:  
   // 滚动数组  
   int uniquePaths(int m, int n) {  
     int dp[2][n];  
     for (int i = 0; i < n; ++i) {  
       dp[0][i] = 1;  
     }  
     dp[1][0] = 1;  
     int row = 0;  
     for (int i = 1; i < m; ++i) {  
       row = !row;  
       for (int j = 1; j < n; ++j) {  
         dp[row][j] = dp[!row][j] + dp[row][j - 1];  
       }  
     }  
     return dp[row][n - 1];  
   }  
 };  
   
 class Solution {  
 public:  
   int uniquePaths(int m, int n) {  
     vector<int> dp(n, 1);  
     for (int i = 1; i < m; ++i) {  
       for (int j = 1; j < n; ++j) {  
         dp[j] = dp[j-1] + dp[j];  
       }  
     }  
     return dp[n-1];  
   }  
 };