一个比较naive的版本，使用的空间是O（MxN）,
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0]=1;
for(int i = 0;i<m;i++)
{
int pos = i==0?1:0;
for(int j = pos;j<n;j++)
{
dp[i][j]=helper(dp,i-1,j)+helper(dp,i,j-1);
}
}
return dp[m-1][n-1];
}
private int helper (int[][] dp ,int m ,int n )
{
if(m<0||m>=dp.length)return 0;
if(n<0||n>=dp[0].length)return 0;
if(m==0||n==0)return 1;
return dp[m][n];
}
}
如果注意到表达式dp[i][j]=dp[i-1,j]+dp[i,j-1];只和上一次的状态和这一次前面的状态有关，那么可以优化到0（N）。
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int [n];
for(int i = 0 ;i<n;i++)
{
dp[i]=1;
}
for(int i = 1;i<m;i++)
{
for(int j = 0 ;j<n;j++)
{
dp[j]+=j==0?0:dp[j-1];
}
}
return dp[n-1];
}
