原题链接：https://leetcode.com/problems/unique-paths/ A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there? Above is a 3 x 7 grid. How many possible unique paths are there? Note: m and n will be at most 100.
给出一个矩阵，从左上角走向右下角，只能选择向右或者向下，一共有多少种不同的走法？
这是一条经典的动态规划题，假设矩阵的长是n，宽是m，设一个hash[ m ][ n ] 数组，hash[ i ][ j ]表示走到第 i 行第 j 列的方法数，由于只能向右或者向下走，那么很明显，原来矩阵的第一行和第一列的hash值都是1，因为只有一种走法。 剩下的部分，对于任意的hash[ i ][ j ]： hash[ i ][ j ] = hash[ i ][ j - 1] + hash[ i -1 ][ j ]，因为走到 （i，j）位置只能由（i - 1，j）往下走，或者（i，j - 1）往右走，故走到该点的方法数等于走到上述两点方法数的和。这样可以从左到右，从上到下遍历数组，最后hash[ m - 1 ][ n - 1 ]的值就是最终的结果。 有了上面的思路，我们可以用滚动数组的方法压缩一下空间，只开一个hash[ n ]数组，然后每次hash[ i ] = hash[ i - 1 ] + hash[ i ]的方式来刷新，最后的hash[ n - 1 ]就是最后的答案。
代码如下：
class Solution { public: int uniquePaths(int m, int n) { int hash[n]; // 第一行的走法都是1 for (int i = 0; i < n; ++i) hash[i] = 1; for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { hash[j] = hash[j - 1] + hash[j]; } } return hash[n - 1]; } };