课件下载地址

精选留言(14)

• 
  预见

  2018-11-25

  初始化棋盘
  m, n = 8, 8
  matrics = [['空地' for i in range(m)] for i in range(n)]
  matrics[0][2], matrics[2][2], matrics[5][5], matrics[6][7] = 0, 0, 0, 0
  
  def count_path(start_x, start_y):
      # 声明状态变量，用于记忆。这里是二维棋盘，所以用二维数组存储。
      opt = [[0 for i in range(m)] for i in range(n)]
  
      for i in range(m-1, start_x-1, -1):
          for j in range(n-1, start_y-1, -1):
              # 不考虑石头在最低行和最右列的情况
              if i == m-1 or j == n-1:
                  opt[i][j] = 1
              else:
                  # 如果这个位置是空地，则说明可以行走
                  if matrics[i][j] == '空地':
                      # 递推公式
                      opt[i][j] = opt[i+1][j] + opt[i][j+1]
                  else:
                      opt[i][j] = 0
      print(opt)
      return opt[start_x][start_y]

  展开

  作者回复: 👍🏻😀

  

   9
• 
  邓桥

  2018-12-16

  讲的太好了，学到最有用的一个词 递推

  

   5
• 
  William

  2019-02-20

  // JavaScript自底向上的写法
  // 迷宫从左上角走到右下角共有多少种走法
  // dp(i, j) = dp(i+1, j) + dp(i, j+1)
  let count_path = (mat) => {
      let rows = mat.length, cols = mat[0].length;
      let opt = new Array(rows).fill(0).map(_item => new Array(cols).fill(0));
      for (let i = rows - 1; i >= 0; --i) {
          for (let j = cols - 1; j >= 0; --j) {
              if (mat[i][j] === 1) { // 障碍物
                  opt[i][j] = 0;
              } else if (i === rows - 1 && j === cols - 1) { // 终点
                  opt[i][j] = 0;
              } else if (i === rows - 1 || j === cols - 1) { // 下边缘 & 右边缘
                  opt[i][j] = 1;
              } else {
                  opt[i][j] = opt[i+1][j] + opt[i][j+1]; // 递推
              }
          }
      }
      return opt[0][0];
  };
  // --- test ---
  let mat = [[0, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 1, 0, 0, 0, 1, 0],
              [0, 0, 0, 0, 1, 0, 0, 0],
              [1, 0, 1, 0, 0, 1, 0, 0],
              [0, 0, 1, 0, 0, 0, 0, 0],
              [0, 0, 0, 1, 1, 0, 1, 0],
              [0, 1, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0]];
  console.log(count_path(mat)); // 27
  

  展开

  作者回复: 帅！！

  

   3
• 
  hallo128

  2018-12-18

  若为m*n的棋盘：
  （1）从[1,1]位置开始算
  应该是：向下m-1步，向右n-1步。
  在所有的m+n-2步中选择m-1步向下，因此总走法是C(m+n-2, m-1)。
  （2）若从顶格算（人开始的位置不在棋盘内），才是向下m步，向右n步，总走法为C(m+n, m)。
  不过从视频的图来看，应该是第一种排列组合情况。

  展开

  

   3
• 
  邱

  2019-11-27

  没看到Java版本，Java也可以很优化。
  public int countPaths(boolean[][] grid, int row, int col) {
      int[][] opt = new int[row][col];
      for (int r = row - 1; r >= 0; r--) {
          for (int c = col - 1; c >= 0; c--) {
              if ((r == row - 1) || (c == col - 1)) {
                  opt[r][c] = 1;
              } else if (grid[r][c]) {
                  opt[r][c] = 0;
              } else if (!grid[r][c]) {
                  opt[r][c] = opt[r + 1][c] + opt[r][c + 1];
              }
          }
      }
      return opt[0][0];
  }

  展开

  

   1
• 
  蔡雪钧

  2019-04-09

  感觉是不是应该从start开始推吧？从end开始推的话遇到石头就不对了。因为只能往右或者往下走吧？

  作者回复: 再好好想想。这里数据里存的是走到最右下方格子的总次数。

  

   1
• 
  贱贱的梦想

  2019-11-05

  教案做的很好

  作者回复: 感谢肯定！

  

  
• 
  Barnett

  2019-10-11

  def countPaths(grid : Array[Array[Int]], row : Int, col : Int) : Int = {
          var opt = Array.fill(grid.length)(Array.fill(grid(0).length)(0))
          for (i <- (0 until(grid.length)).reverse) {
              for (j <- (0 until(grid(0).length)).reverse) {
                  val status = grid(i)(j)
                  if (status != 1) {
                      if (i == grid.length - 1 && j == grid(i).length) {
                          opt(i)(j) = 0
                      } else if (i == grid.length - 1) {
                          //最下边一行 为1
                          opt(i)(j) = 1
                      } else if (j == grid(i).length - 1) {
                          //最右边一行 为1
                          opt(i)(j) = 1
                      } else {
                          //等于 下面的 + 右边的
                          opt(i)(j) = opt(i + 1)(j) + opt(i)(j + 1)
                      }
                  }
  
              }
          }
          opt(row)(col)
      }
  
      def main(args: Array[String]): Unit = {
          var mat = Array(
                          Array(0, 0, 0, 0, 0, 0, 0, 0),
                          Array(0, 0, 1, 0, 0, 0, 1, 0),
                          Array(0, 0, 0, 0, 1, 0, 0, 0),
                          Array(1, 0, 1, 0, 0, 1, 0, 0),
                          Array(0, 0, 1, 0, 0, 0, 0, 0),
                          Array(0, 0, 0, 1, 1, 0, 1, 0),
                          Array(0, 1, 0, 0, 0, 1, 0, 0),
                          Array(0, 0, 0, 0, 0, 0, 0, 0))
          print(countPaths(mat, 0, 0))
      }

  展开

  

  
• 
  ttttt

  2019-10-07

  如果没有石头的情况：排列组合公式
  
  是一个组合问题。对方向编号，向上是0，向右是1，那么从左下角走到右上角一定要经过M 个1和N个0。这个题目可以转化为从M+N个盒子中挑出M个盒子有多少种方法。
  
  就是C(M+N, M), 或者C(M+N, N).
  
  所以2 * 2的格子有C(2+2, 2)=6中走法,  2* 3 的格子有 C(5, 2)=10种走法。

  展开

  作者回复: 对的，赞！

  

  
• 
  陈志恒

  2019-09-28

  1.最优子结构（最优子问题）是递推（动态规划）的基础。子问题是否存在：问题规模缩小，但问题没变。正向：采用递归，不断缩小子问题。逆向：递推，利用递推公式不断放大子问题
  2.贪心思考的是：当前位置最优“结果”。
  3.动规思考的是：当前位置最优“子问题”。子问题表现为一种结构，不是直接的结果
  4.递推的技巧：只考虑“一步”，并从中定义出子问题

  

  
• 
  ZHU～JM

  2019-08-09

  opt[i][j] = opt[i+1][j] + opt[i][j+1]

  

  
• 
  infrared628

  2019-06-21

  上面的JavaScript版本代码有点bug，右边缘的下方如果为0那上面的格子都应该为0，下边缘的右方的格子如果为0那左面的格子都应该为0，否则无法处理[[0,0,0],[1,1,1],[0,0,0]]这样的情况，另外那个corner case处理也有点问题，Java如下：
  class Solution {
      public int uniquePathsWithObstacles(int[][] obstacleGrid) {
          if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
              return 1;//原地踏步算一条
          }
          int rows = obstacleGrid.length;
          int cols = obstacleGrid[0].length;
  
          int[][] dp = new int[rows][cols];
  
          for (int i = rows - 1; i >= 0; i--) {
              for (int j = cols - 1; j >= 0; j--) {
                  if (obstacleGrid[i][j] == 1) {//障碍物，这个条件要先检查
                      dp[i][j] = 0;//设为从当前点到终点的路径数为0
                  } else {
                      if (i == rows - 1 && j == cols - 1) {//在右下角的终点处，自己走到自己，一条路
                          dp[i][j] = 1;
                      } else if (i == rows - 1) {//最后一列除了最右下角的格子
                          if (dp[i][j + 1] == 0) {//最后一列如果下面的路被堵住了，上面的格子均为0条路径
                              dp[i][j] = 0;
                          } else {
                              dp[i][j] = 1;
                          }
                      } else if(j == cols - 1) {//最后一行除了最右下角的格子
                          if (dp[i + 1][j] == 0) {//最后一行如果右面的路被堵住了，左面的格子均为0条路径
                              dp[i][j] = 0;
                          } else {
                              dp[i][j] = 1;
                          }
                      } else{
                          dp[i][j] = dp[i + 1][j] + dp[i][j + 1];//正常的递推式
                      }
                  }
              }
          }
          return dp[0][0];
      }
  }
  
  

  展开

  

  
• 
  ssala

  2019-05-25

  这课听起来简直是一种享受。老师分享的许多观点很受用，让人有一种恍然大悟的感觉。动态规划其实是动态递推；最优子结构表明我们在求解问题最优解的过程中也是在求解子问题的最优解；解题时只关注当前阶段和下一阶段，不要陷入细节，否则会让自己疑惑；推导出递推公式时要相信这个公式。

  

  
• 
  CarreyWang

  2019-01-12

  我觉得直接从start开始进行这种递推好像也可以，每一个状态等于他的上一个与左边这个的值，最后的出来应该也可以，如果是石头也为0，不知道对不对？

   1

  