第160题 实现机器人走方格

如下图，有m*n个格子，一个人从左上角start位置，每次只能向下或向右移动一步。要走到右下角finish位置，总共有多少条路径

实现

• 如果只走第一行就只有一条路径
• 如果只走第一列，也只有一条路径
• 其他走法，根据这个公式 map[i][j] = map[i-1][j] + map[i][j-1]，如走到[5,4]的路径数，就是[4,4]和[5,3]的路径数之和 -- 动态规划的思想

    // m行 n列
    function getPaths(m, n) {
      // m * n二维数组，模拟网格
      const map = new Array(m)
      for(let i = 0; i < m; i++) {
        map[i] = new Array(n) // 行对应的列
      } 
      // 如果只走第一行就只有一条路径，所以第一行所有item都填充1
      map[0].fill(1)
    
      // 如果只走第一列，也只有一条路径。所以第一行item都填充1
      for(let i = 0; i < m; i++) {
        map[i][0] = 1
      }
    
      /**此时map结果
       * [
        * [1, 1, 1, 1],
          [1, emptyx3],
          [1, emptyx3],
          [1, emptyx3],
          [1, emptyx3]
         ]
       */
      
      // 其他item，根据这个公式 map[i][j] = map[i-1][j] + map[i][j-1]
      // 如走到[5,4]的路径数，就是[4,4]和[5,3]的路径数之和 -- 动态规划的思想
      // 注意：i和j都是从1开始，因为0的位置已经被上文赋值了
      for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
          map[i][j] = map[i-1][j] + map[i][j-1]
        }
      }
    
      /**此时map结果
       * [
        * [1, 1, 1, 1],
          [1, 2, 3, 4],
          [1, 3, 6, 10],
          [1, 4, 10, 20],
          [1, 5, 15, 35]
         ]
       */
    
      // 返回完成的节点的路径数
      return map[m-1][n-1]
    }
    
    console.log(getPaths(5, 4)) // 35