课件下载地址

初始化棋盘 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]

// 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

如果没有石头的情况：排列组合公式 是一个组合问题。对方向编号，向上是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种走法。

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

教案做的很好

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

没看到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]; }

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

若为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)。 不过从视频的图来看，应该是第一种排列组合情况。

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