62. Unique Paths

一个比较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];
    }