62.Unique-Paths.md

62. Unique Paths

题目链接

• 一、描述 机器人从左上角走到右下角，有多少种方法。只能向右/向下，每次挪动一步。

• 二、思路

  1. 确定状态
     • 最后一步：向右，向下。设右下角坐标是[m-1,n-1]，则倒数第二步的位置，就是[m-2,n-1]或者[m-1,n-2]。
     • 子问题：假设从左上角走到[m-2,n-1]有X种走法，走到[m-1,n-2]有Y种走法，则机器人有X+Y种方式走到[m-1,n-1]。问题转化为：从左上角走到[m-2,n-1]和[m-1,n-2]，有多少种方法
  2. 转移方程
  3. 初始条件、边界情况
     • 初始条件：f[0][0]=1
     • 边界情况：f[i][0]=1，f[0][j]=1（即第一行、第一列初始化为1）。
  4. 计算顺序
     • 两重for循环初始化：第0行（f[0][0],f[0][1],...f[0][n-1]），...，第m-1行（f[m-1][0],...,f[m-1][n-1]）
     • 为了使得转移方程右边需要的项已经被计算过，这里第0行到第m-1行，或者从第0列到n-1列，都是可行的。
     • f[m-1][n-1]就是我们想要的结果
  5. 时间、空间复杂度：O（m*n）

• 三、实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        int i,j, f[m][n];
        for(i=0; i<m; i++)   f[i][0]=1;
        for(i=0; i<n; i++)   f[0][i]=1;

        for(j=1; j<n; j++)      //这两个for可以交换      
            for(i=1; i<m; i++)
                f[i][j] = f[i-1][j] + f[i][j-1];
        
        return f[m-1][n-1];
    }
};