不同路径

题目

一个机器人位于一个 m x n 网格的左上角。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。

问总共有多少条不同的路径？

思路

定义dp[i][j]表示从起点到点(i,j)的不同路径，则答案为dp[m-1][n-1]。i==0或者j==0,dp[i][j]=1;
dp[i][j] = dp[i-1][j]+dp[i][j-1]，计算顺序为i从0到m、j从0到n

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,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];
    }
};

空间优化一

观察上述代码，dp[i][j]只与当前行的dp[i][j-1]和上一行的dp[i-1][j]有关。上上行及之前的空间都没用了。所以可以优化。定义cur和pre两个一维数组。cur表示当前行，pre表示上一行，这两个数组循环使用。答案为cur或者pre的最后一个数。

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> pre(n,1),cur(n,1);
        for(int i = 1;i < m;i++) {
            for(int j = 1;j < n;j++) {
                cur[j] = pre[j]+cur[j-1];
            }
            for (int j = 1;j < n;j++) {
                pre[j] = cur[j];
            }
        }
        return pre[n-1];
    }
};

空间优化二

观察上述代码，第一层for循环，每次执行前后，cur 和 pre 的值是一样的，即pre[j]和cur[j]是相等的。把cur[j] = pre[j]+cur[j-1]替换为cur[j] = cur[j]+cur[j-1],效果是等价的。所以可以进一步优化成一个一维数组。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> cur(n,1);
        for(int i = 1;i < m;i++) {
            for(int j = 1;j < n;j++) {
                cur[j] = cur[j]+cur[j-1];
            }
        }
        return cur[n-1];
    }
};