下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 44 | 理论理解:动态规划(下)
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享
本节摘要

精选留言(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
  • 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
  • 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
    教案做的很好

    作者回复: 感谢肯定!

  • 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))
        }
    展开
  • 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.递推的技巧:只考虑“一步”,并从中定义出子问题
  • 2019-08-09
    opt[i][j] = opt[i+1][j] + opt[i][j+1]
  • 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];
        }
    }

    展开
  • 2019-05-25
    这课听起来简直是一种享受。老师分享的许多观点很受用,让人有一种恍然大悟的感觉。动态规划其实是动态递推;最优子结构表明我们在求解问题最优解的过程中也是在求解子问题的最优解;解题时只关注当前阶段和下一阶段,不要陷入细节,否则会让自己疑惑;推导出递推公式时要相信这个公式。
  • 2019-01-12
    我觉得直接从start开始进行这种递推好像也可以,每一个状态等于他的上一个与左边这个的值,最后的出来应该也可以,如果是石头也为0,不知道对不对?
    1