题解 | #求路径# 空间优化

经典动态规划的方程为： dp[i][j] = dp[i][j-1] + dp[i-1][j]

因为只要求解总路径数，dp[i][j]只与左边和上边的状态有关，不需要保存中间状态。

因而可以只用一个数组来保存。当前需要更新的黄色的dp[j]为：刚更新的dp[j-1] 与 旧的dp[j]值之和。

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        int less = m >= n? n: m;
        int more = n >= m? n: m;
        vector<int> cnt(less);
        fill(cnt.begin(), cnt.end(), 1);
        for(int i = 1; i < more; i++){
            for(int j = 1; j < less; j++){
                cnt[j] = cnt[j] + cnt[j-1];
            }
        }
        return cnt[less-1];
    }
};

时间复杂度O(m*n), 空间复杂度O(min(m,n))