LeetCode 62 不同路径

dfs(超时)

class Solution {
public:
    int res = 0;

    void dfs(int x, int y, int m, int n) {

        if (x == m && y == n) res ++;

        if (x + 1 <= m) dfs(x + 1, y, m, n);
        if (y + 1 <= n) dfs(x, y + 1, m, n);
      

    }
    int uniquePaths(int m, int n) {
        dfs(1, 1, m, n);

        return res;
    }
};

动态规划

// 7 * 3
/*
1 1 1 1  1  1  1
1 2 3 4  5  6  7
1 3 6 10 15 21 28
*/

const int N = 110;
class Solution {
public:
    int dp[N][N];
    int uniquePaths(int m, int n) {
        for (int i = 0; i < m; i ++) dp[i][0] = 1;
        for (int i = 0; i < n; i ++) dp[0][i] = 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];
    }
};