机器人到右下角的路径

---

题目描述

一个机器人在m×n大小的地图的左上角（起点，下图中的标记“start”的位置）。

机器人每次向下或向右移动。机器人要到达地图的右下角。（终点，下图中的标记“Finish”的位置）。

可以有多少种不同的路径从起点走到终点？

解题思路

一开始我想到的是用回溯法，标记已经走过的点，但是后来发现错了即使走过的点还可以重新经过呀呀呀:joy_cat:

然后又想，二叉树根到叶子结点的路径问题，发现也不对.

然后想到前面的判断子序列个数的动态规划问题，似乎是通过借助矩阵的方式解决的。

然后尝试着找了几个点的路径得到了这个图

根据题意机器人只能向右，向下行走，反过来想到终点路径的数量应该是终点的左点和上点的路径之和。所以目的就明确了求出当前点的上点和左点分别的路径数量。

通过归纳法可知，与机器人同行或同列的终点，路径只有一条。

构造一个m×n的矩阵dp，并且都初始化为1.到每个点的路径为：

dp[][]=dp[i][j-1] + dp[i-1][j]

接下来请看代码部分，通过代码会更加清晰的理解整个过程。

代码

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][j-1] + dp[i-1][j];
          }
      return dp[m-1][n-1];
  }
};

同样类似子序列个数问题，也可以对上述代码进行优化，只是用一维数组即可：

class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<int> dp(n, 1);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (i * j != 0)// 不是第一行或第一列
                    dp[j] = dp[j] + dp[j - 1];
            }
        return dp[n-1];
    }
};

参考链接：https://www.nowcoder.com/questionTerminal/166eaff8439d4cd898e3ba933fbc6358?f=discussion