ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

算法:记忆化和动态规划 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

算法:记忆化和动态规划

Algorithms: Memoization and Dynamic Programming

大家好 我是《程序员面试金典》的作者 盖尔·拉克曼·麦克道尔
Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.
今天我们讲个很重要的部分 记忆化与动态规划
Today I want to talk about memoization and dynamic programming. This is a super important topic.
一开始可能比较难理解 但是一旦学会了 你就会发现其实很简单
It’s challenging a bit at first but once you get the hang of it it gets a lot easier.
斐波那契数列是个典型的递归案例
Fibonacci’s pretty much the classic recursive example.
其中第 n 项是 n-1 项与 n-2 项的和
Fib of n is the sum of fib of n minus 1 plus fib of n minus 2.
初始条件为第0项为0 第1项为1
And then we need some starting conditions like if f of 0 is 0 and and fib of 1 is 1.
很容易就能写出数列的前几个数
And we can very easily write out the first few cases here.
现在考虑下编程实现
But now let’s think about the code.
代码其实很简单
So transation this into code is very straight forward as well.
但是要考虑运行时的一些问题
But there’s a problem when you think about the runtime here.
假如我们调用 fib(6) 那么fib(6)就会调用 fib(5) 与 fib(4) fib(5)会调用fib(4)与fib(3) fib(4)会调用 fib(3)与fib(2) 等等
So if we call this for say fib of 6, fib of 6 will call fib of 5 and fib of 4, 5 will call 4 and 3, 4 will call 3 and 2 etc etc.
直至出现初始条件 我们需要计算所有的分支
Then we finish a single branch and we still need to do all the other branches.
这样会很低效 尤其是在调用 fib(n)时
So that’s going to get very very inefficient, specifically if we imagine calling this for say fib of n,
会一直循环调用下去 总共要调用 n 层
we are going to call fib of n, and that’s going to call n, fib of n minus one, fib of n minus 2, fib of n minus 3, all the way down, to roughly n levels.
导致树里面有 n 层 第一层有一个节点 第二层有两个节点
So we’ll have n levels in our tree. The first level will have one node, the second level will have two nodes.
每个节点有两个子节点 第三层有四个节点 第四层有八个节点等等以此类推
Each node has two children, so we will have four nodes of the next level, then 8 and so on and so on.
每多一层节点倍数就要再多 2的n次方个
So if you take one you double it n times because we have double the number nodes at every single level,
那么最后树总共会有 2的n次方-1个节点
we’re gonna wind up with roughly 2 to the n nodes in the tree.
时间复杂度为 2的n次方
So this gives us a runtime of O of 2 to the end,
但是如果手算就没有这么慢 所以算法可以改进
and if you remember I was able to compute this by hand fairly quickly and so there’s a bit of a mismatch here.
为什么这个算法如此低效呢
Why is this algorithm so inefficient?
因为一直在计算重复的值
And the reason is that we keep doing things repeatedly.
第4项计算了2次
We compute the fib of 4 twice, here and here.
第3项计算了3次
Fib of 3 gets computed 3 times here, here, and here.
第2项计算了5次
Fib of 2 gets computed five times, here, here, here, here, and here.
显然这些值都没发生变化 第三项第四项的值没变过
Now obviously these values haven’t changed, fib of 4 is always the same thing, fib of 3 is always the same thing.
我们就可以只算一次这些数值
So what we should be able to do is just compute these values once
如果再需要的话 直接返回存储的值
and if we ever have to repeat them again just return the stored value.
每次使用存储的值而不是重新计算
So we store the value each time rather than computing it from scratch.
这就是记忆化算法的实现过程
And that’s what the most basic implementation of a memoization algorithm is.
现在我们再看看代码所做的 仍然是沿着这些路径计算
So now if we walk through what this code does we’re we are still going to go and compute this whole path down here
但是计算的同时会构建存储表
but when we do that we’re going to build up this table.
首先计算第一项然后计算第二项 由于第二项已经计算过了
So then when we get down to computing fib of 1, that’s a base case, fib of 2, hey already been computed
可以直接返回存储的值 第三项第四项都被计算过了
we just return the value. Fib of 3, already computed, fib of 4, already computed.
尽管同之前一样要递归到同样的深度
So although we still recurse just as deeply
但除了计算基本的值外 我们还使用了计算后存储的值
all our other work has been done by that point and we’re just returning stored values.
现在的时间复杂度是线性的而不是指数的了 这算得上是巨大的提升
And now we get a linear runtime instead of exponential which is of course an enormous improvement.
现在看看空间复杂度
So now let’s talk about space complexity.
空间复杂度由使用的内存决定
Space complexity comes from any memory you use,
包括创建的数组或变量 还包括调用的栈
and that includes yet things like creating arrays and stuff like that but it also includes the call stack.
我们先看看没使用记忆化算法的空间复杂度
So let’s think about the space complexity of the non memoized solution.
许多人认为是指数级的 但实际不是
A lot of people describe this as of O of 2 to the n and that’s actually a mistake.
大多人认为既然调用栈上有2的n次方左右的空间 那么空间复杂度就是2的n次方了
People were thinking well gee all O of 2 to the n things are all on the call stack so we need all of that.
是的 但是这些数据并不同时在调用栈上
Yes but they’re not all on the call stack at the same time.
一种通俗的解释就是 如果我给你一块内存空间来运行程序
One way to think about space complexity is, if I were to give you a chunk of memory to run your program
内存空间要多大才够呢?
how big would that chunk of memory have to be?
尽管指数级的数据会填充调用栈
Although all O of 2 to the n things wind up on the call stack overall time,
但并不是同时都在栈上的
they’re not all sitting here at the same time.
调用堆栈最深时就是内存占用最高的时刻
The biggest your call stack ever gets, the most memory you have used at any one point in time, is O of n.
在某个时刻堆栈的层级n就是对象的数量
There’s only O of n things that wind up on the call stack at any one given time.
所以非记忆化算法的空间复杂度是O(n)
So the space complexity, the non-memoized solution is O of n.
记忆化算法空间复杂度也是O(n)
The memoized solution also has a space complexity of O of n,
因为调用的时候依然会调用到树的底层 还另外需要n块空间存储记忆表
because we need O of n memory for the call stack still and we need another O of n memory for the memo table.
但是O(n)加 O(n)仍然是O(n) 所以两者都是O(n)的空间复杂度
But O of n plus O of n is still O of n. So both of these have a space complexity of O of n.
现在我们换个问题来试试
Now let’s try this out on a new problem.
假定有个n*n的正方形棋盘 其中一些格子被占用了 而你只能向下或向右移动
Suppose you’re given an n-by-n grid and you can only move down or to the right and certain cells are blocked off in this grid.
那么从左上角到右下角有多少种不同的移动路径呢?
The question is, how many paths are there from the top left to the bottom right?
很容易想到可以利用递归求解 那么我们来分而治之
As you might guess, we want to approach this recursively, so let’s break this down into smaller problems.
首先 大问题是从左上到右下有多少种不同的走法
The first, the overall problem is, how many paths are there from the top left to the bottom right.
起点是左上角的绿色小人处
Well let’s think about this green guy in the top left corner.
首先要决定是向下还是向右移动 这也是唯二的选择
The first decision he needs to make is, well am I going to go down or to the right. Those are my only options.
把这些标出来
So let’s picture each of those options.
只有两个移动的方向
There are only those two ways of going.
左上到右下的走法
So the number of paths from the start to the end
是位置a但右下的走法 加上位置b到右下的走法
is the number of paths from position a to the end plus number number paths from position B to the end.
这样问题就得到了分解
So now we’ve broken down our problem into other sub problems.
接下来呢?
So now what happens?
a位置要么向下要么向左移动
Well person A has to go either down or to the right again.
b位置也是同理 现在a位置的问题变成了c d位置的问题
Same with position B. So now the number of paths from A to the end can be broken down into C&D.
a位置的走法数量 是c与d走法的和
Its number of paths from C to the end plus the number of paths from D to the end.
b也同理 是c位置与e位置走法数量的和
Same thing with B. Its number of paths from B to the end, is number paths from C to the end, plus the number of paths from E of the end.
递归会到终点停止 给出确切的答案
This recursion stops when we have a definitive answer and that comes when you’re actually at the end.
最后一步 即从终点到终点的走法是1
The number of paths from the end to the end is just 1.
原地踏步 这形成了递归的基本条件
You stand exactly where you are. So that forms our recursion base cases.
将此转化为代码也不难
Translating this into code is relatively straight forward.
不越过边界且不走被填充方块的情况下 只要一直向下或者向右走即可
We just traverse down and to the right, obviously making sure we check you know they’re not out of bounds or in a blocked-off square,
只要将向下与向右的走法数量递归相加即可
but then we just sum up the number of ways of going down plus the number of ways of going to the right.
而到达右下角终点时返回1即可
And when we get down to the actual end we return 1.
这就是算法的直接实现
This is a pretty straight forward implementation of that algorithm,
方形的作用是不要出界 不要走被填充的方块
valid square does both the boundary checking as well as making sure we’re not in a blocked-off square.
如果碰到边界或填充块则认为是0
If we are then we turn 0 because there’s no path,
右下角终点处返回1 因为只有一种走法 原地踏步
if we’re at the end return one because there’s just the one path, you stay right there.
而当前需要计算方格处数据是向下移动后走法数量加上向右移动后走法数量之和
Otherwise number of paths from here to the end is the number of paths going down to the end, and plus the number of paths going right the end.
我在做这种题时的一点建议就是使用行列而不是xy等变量名
One little tip by the way whenever I do a matrix problem I like to use row and columns for my variable names rather than x and y.
x即等价于列 而y即等价于行
And the reason is that the x-coordinate actually translates to columns and the y-coordinate translates to the rows.
但是以xy区分行列反而是画蛇添足
But people tend to instinctively write grid of X comma Y, and that’s backwards.
比如(y,x) 就比直接说几行几列要稍显复杂
It should be grid of Y comma X. It just leads to a lot of confusion.
相信我 别用xy处理矩阵 而用行与列
So take it from me, don’t use X&Y when you deal with matrices, use rows and columns instead.
之前的例子里 我们算了两次c位置处的走法数量
Well one thing we might notice is that in the example above we compute the number of paths from C to the end twice, and that’s unnecessary.
记忆化的做法是 如果计算过则直接返回保存的值
What we should be doing is saying, hey if I’ve already computed something just return that stored value.
所以每计算出一个结果 都存储起来 一旦需要立刻返回存储的值
So every single thing I compute I want to just store that value and return it if I’m ever asked for it again.
这就是记忆化算法
And that’s a memoization approach.
一次计算 立即存储
Now instead we just compute it once and then if we ever need that value again
需要调用 直接返回
just return that stored value and that’s all we have to do here.
时间复杂度是 O(n^2) 因为有n的平方个可能的格子
The runtime now is O of n squared, because we have n squared possible cells that we have to compute this form,
而每个格子计算时 时间是常数级的
but each time we compute it, its constant time given that we have other work already done.
所以总得时间复杂度是O(n^2)
So that gives us a runtime of O of n squared.
这个问题还可以用动态规划来解决
So if we want to we can flip this around and do more of a traditional dynamic programming approach.
我们来看看是怎么做的
So let’s take a look at how this would work.
递归方法的初始值是这两个格子
If we think about what the recursive approach does, the very first concrete values it gets other than the base cases are these two cells.
这是两个明确的值
So that gives us two concrete answers.
再倒推怎么推呢?
Now where can we go from here?
如果倒推的话 接下来应该填这3个格子
Well the next thing if we take that recursion one step up, the next thing it does is it might be filling in one of these three cells.
先从这个开始吧
So let’s start with this one here.
这几个格子的数字是一样的都是1
Well we know the answer to that cell and that cell and that cell and that cell and that cell.
这些格子到终点的路径只有这一条
All of these cells have just one path from the, from their cell to the end which is this path here.
那么这个格子呢?
Now what about this cell here?
如果有向右与向下的走法 此处应该是它们数字之和
Well if there’s one path going down, one path one to the right, the actual answer is their sum.
这里是2条路径 这的数字是1
So there’s two paths there. Now here again one path there.
这可以向下或者向右
Now when we go to this cell there are two paths going down or to the right.
这里的和是2 右边与下边格子数值的和
The sum is going to be these two, the sum of those two cells.
这里可以向下或者向右
And this one here, well we can go down or go to the right.
右侧是2 下边是1
There’s two paths to go to the right, one path if we go down.
所以此处的走法数量是3
So the actual result for the number of paths from this cell to the end is three paths.
如果觉得不妥我们可以走一边检查一下
And we could double-check that if we want.
第一种走法是向下然后一直向右 第二种是向右 向下 再一直向右
One path is going down and then all the way over, another path is going to the right, down, and then all the way over,
第三种是向右 向右 再向下 再一直向右
or to the right, to the right again, down, and all the way over.
所以总共是3种走法
So sure enough, yes, there are three paths.
整个棋盘都可以利用这种方法计算路线数量
And we can do this exact approach going through the entire grid,
从左下向左 抱歉
starting from the bottom left moving to the left, sorry,
从右下一直向左 然后计算上一行
starting from the bottom right, moving all the way to the left, up one row,
从右向左 再向上一行从右向左挨个格子计算
all the way to the left, up one row all the way to the left, filling in these values as we go.
这里是1 这是1 这里是0
So we got a 1, a 1, actually it’s 0 here,
因为这既不能向下 也不能向右
because there’s actually no paths from this cell down to the right.
这是3 因为只能向下走 这也是3 因为只能向右走
And here they’ll be three, because we can only go down. Here three again, we can go only go to the right.
4 1 1 1 1 1 这是3 这是7 1 2 1 2
4, 1, 1, 1, 1, 1, and then 3 here, 7 here, 1, 2, 1, 2
直至用这种方法把表格填满
and we can go through and fill in the entire cell, entire matrix this way.
时间跟空间复杂度都是O(n^2)
Our runtime is still O of n squared and so is our space complexity
但我们少用了些内存因为不再需要调用栈了
But we’ve reduced the actual amount of memory use slightly because we no longer have to use a call stack.
这就是解决问题的不同方法
So these are a couple different ways of approaching problems.
递归思想的使用能够使得问题得到简化
You can tackle things recursively, that’s often a pretty good way to get your handle on the problem in the first place.
进而可以使用记忆化 用记忆表来实现上面的计算
Then you might implement a memoization approach and just throw in a memo table,
记忆表可以是哈希集合 哈希表 或是数组 都可以
maybe that’s a hash set, a hash table, maybe just a simple integer array will work.
当然有时也可以用传统的动态规划迭代解决问题
And sometimes you can easily flip that around and implement an iterative traditional dynamic programming approach.
我强烈建议你在面试前练练这些题
So try these problems out, I really recommend before your interview practicing a whole bunch of these.
这些问题很有规律 一旦掌握了窍门 很容易解决
These problems are actually pretty formulaic and once you get the hang of them they can be very very easy to tackle.
但一开始可能有点棘手 所以加油练习吧 祝你好运
But when you start off first they can be kind of tricky. So do your best, practice these, and good luck.

发表评论

译制信息
视频概述

本视频介绍了记忆化算法与动态规划的原理

听录译者

收集自网络

翻译译者

喔喔243

审核员

审核团1024

视频来源

https://www.youtube.com/watch?v=P8Xa2BitN3I

相关推荐