[数据结构与算法]【Leetcode】62. 不同路径

一. 题目信息

1. 描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
题目链接：https://leetcode-cn.com/problems/unique-paths/

2. 示例

输入：m = 3, n = 7
输出：28

二. 解法

1. 动态规划

算法思路：右边加下边为当前的路径数

①. 复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)

②. c++解法

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