跟读练习: What Is Dynamic Programming and How To Use It - 通过视频学习英语口语
选择练习模式
每种模式都会打开全屏练习室。
175 句
如果句子过短或过长,请点击 Edit 进行调整。
1
Hey CSDojo, it's YK here.
2
So in this video I'm going to talk about what dynamic programming is
3
and how to use it and as I explain how it works I'm going to assume that you're already familiar with recursion.
4
So what is dynamic programming exactly?
5
It's actually fairly simple even though it might sound difficult
6
It's basically a way of making your algorithm more efficient by storing some of the intermediate results
7
And it works really well when your algorithm has a lot of repetitive computations
8
So that you don't have to repeat those computations over and over again and
9
I'm gonna give you a concrete example of how it works with Fibonacci sequence
10
So just in case you're not familiar with it Fibonacci sequence is a sequence of numbers
11
that starts with two ones at the beginning and Each number after that is computed by adding up the two previous numbers
12
So the third Fibranch number is 2 because 1 plus 1 equals 2
13
And then the fourth Fibranch number is 3
14
because 1 plus 2 equals 3 and so on and this sequence keeps on going forever
15
So let's say we're trying to solve the problem of finding the n's Fibranch number
16
or writing a function called Fib of n
17
Which takes a positive integer n and finds and returns the n's Fibranch number
18
So if the given n is 3
19
We want to be able to find and return the third free lunch number, which is 2
20
And if the given n is 5, we want to be able to return the fifth free lunch number, which is 5
21
Let's see how we can solve this problem using dynamic programming
22
So if you want to solve a problem using dynamic programming, there are typically three steps you can take
23
The first step is to come up with a recursive solution to your problem
24
And then in your recursive solution, if you notice that there are a lot of repeated computations
25
You can then store some of the intermediate results so that you don't have to repeat those computations
26
This process is also called
27
Memoization or memoize and this is not to be confused with Memorize
28
and I've made that mistake before too and then the third step if you don't like using recursion anymore is
29
To come up with something called a bottom -up approach
30
So let's first see what a recursive solution might look like for this particular problem
31
So as I said earlier, we're going to write a function called fib of n
32
Which takes n a positive integer and returns the nth fibranche number
33
And if n is equal to 1 or 2
34
We know that the first and the second fibranche numbers are 1
35
We're going to return 1
36
But instead of returning it right away
37
We're going to store it in a temporary variable called the result and then return that instead.
38
And it's going to be clear why we need to do that later.
39
And if n is neither 1 nor 2, then we're going to return the sum of the two previous Fibonacci numbers instead.
40
Fib of n minus 1 plus Fib of n minus 2, store that in result, and then return it at the end.
41
So this solution works, but it's very very inefficient.
42
To see why, let's see an example where we are trying to find the fifth Fibonacci number by calling Fibonacci 5.
43
So to find the return value of Fibonacci 5,
44
we need to first compute the return values for Fibonacci 4 and Fibonacci 3 so we can add them up.
45
And to find Fibonacci 4, we need to first compute Fibonacci 3 and Fibonacci 2 and so on.
46
And that's what this diagram shows.
47
And looking at this diagram, you might notice that there are some competitions that we repeat over and over again.
48
For example, we need to compute the return value for Fibonacci 3 times,
49
and we need to compute the return value for Fibonacci 3 twice here.
50
And it's not a big deal when we are trying to find the 5th or 6th Fibonacci number,
51
but if we're trying to find the 100th Fibonacci number, it becomes an issue.
52
And actually the time it takes to find the n's Fibonacci number grows exponentially
53
Or roughly in the order of 2 to the power of n
54
And dynamic programming here says why not just store those return values
55
For example for Fibonacci 3 store the return value once we compute it
56
And then use that same value when we see Fibonacci 3 again instead of computing it again
57
And again, this process is called memoization.
58
So let's see what a memoized solution looks like in code
59
Let's again consider the example where we're trying to find the fifth few months number by calling Fib of 5
60
The idea of this solution is going to be that we're going to use an array whose length is
61
n plus 1 or 6 in this particular case
62
because n here is 5 and then we're going to store the return value for the functional fib of n.
63
at the index n.
64
So we're going to store fib of 1, which is the first fib of number right here at index 1,
65
and then fib of 2 at index 2, and so on.
66
And initially we're going to set all these values to null.
67
And we're going to write our function fib, and this is going to take two arguments instead of just one.
68
The first one is the same as before, n, a positive integer, and the second one is going to be this array
69
and so you'll need to initialize this array memo before you call this function.
70
Now at the beginning of this function, check if memo at index n is null or not.
71
If it's not equal to null, that'll mean that we've already seen this argument n and we've
72
We've already stored the return value for that at the index n in memo, so just return that instead
73
So return memo square brackets n
74
Otherwise, the following part is the same as before
75
If n is equal to 1 or 2, return 1, store 1 in result, and then return that at the end
76
And if that's not the case, then find the sum of the two previous equivalent numbers, and then return that instead
77
And then what's new in this function is that before you return this result, the return value
78
You need to store it in Memo at index n so that you can use it later
79
Let's now think about the time complexity for this solution.
80
We're going to call it t of n
81
This is going to be the time it takes to find the n's Fibonacci number with this particular method and
82
we're going to find that by multiplying the number of times we call this function,
83
fib, with the time it takes to execute each of those calls.
84
We're going to call that t.
85
Now, there are only two ways we're going to call this function fib.
86
The first way is when we call this function for the first time with the arguments n
87
and memo to find the entropy bunch number, and the second way is from this line right here,
88
and And notice that if you look at this whole block after this first if clause,
89
this whole block is only executed at most n times.
90
And this is true because there are n possible arguments to this function.
91
That's 1 through n.
92
And each time this function is called with each of those arguments, the return value will be stored in memo at index n.
93
So after the first time this function is called with each argument, we'll never get to this block.
94
And each time this block is executed, fib is called a most twice if we get to this line.
95
So the number of times fib is called is a most 2 times n plus 1.
96
So 2n comes from this block right here, and 1 comes from the first time we call this function fib and
97
the time it takes to execute each of those calls this t right here is
98
Going to be a constant time or a big O of 1
99
and this is because if you look at each operation in this function excluding
100
These recursive calls that follow each operation is a constant time operation and when you have a constant time operation
101
when you add them up, you still get a constant time operation, which is big O of 1.
102
And that's why we have big O of 1 here.
103
And so t of n, or the time it takes to find the n -spin -onage number with this particular method,
104
is going to be 2n plus 1 times big O of 1, which is big O of 2n plus 1,
105
which is equal to big O of n.
106
and this is a huge improvement from what we had earlier
107
which was big O of 2 to the power of n
108
and let's now examine how this memo array is actually filled
109
so let's say we're trying to find the fifth Fibonacci number again
110
and when we call fib with the argument 5
111
and memo of course we'll see
112
that we don't have a stored value at the index 5 yet
113
so we go down and we're gonna to ask ourselves what's the value of Fib of 4
114
and then 3 and so on and when we get to Fib of 2
115
we'll know that this value is 1 so we're going to store it at index 2 right here,
116
and same with Fibon1, that's 1 right here, and once we have these two values, we'll be able to find the third Fibonacci number,
117
which is Fibon3 right here, and then once we find the value by adding them up,
118
store that value right here so we can use it later, and then when we go up to Fibon4,
119
we'll add 1 and 2 right here and we get 3
120
and so on until we get here and
121
so as you can see this array is mostly filled from left to right so
122
when you see this you might say why not just explicitly build
123
this array from left to right from scratch instead of building it recursively
124
and that's the idea behind a bottom -up approach
125
so let's see what a bottom -up approach might look like in code
126
we're going to define a function called fib bottom up
127
which takes n a positive integer just like before
128
and returns the nth Fibonacci number and then
129
if n is equal to 1 or 2 of course we're going to return 1 and after
130
that we're going to define an array whose length is going
131
to be n plus 1 where n plus 1 is 6 of course
132
if we're trying to find the fifth Fibonacci number right here
133
if n is equal to 5 and after
134
that we're going to set the first and the second elements of this array bottom -up to be 1, these two items right here,
135
and then we're going to run a for loop for i from 3, which corresponds to this item right here,
136
up to n, and n corresponds to the last item right here of this array,
137
and whatever index we're examining currently we're going to set
138
that element at the index i
139
or bottom up square brackets i to be the sum of the two previous items
140
so in this particular example we'll have two here three here
141
and after that we're going to return the last item in bottom up
142
or bottom up square brackets n
143
and we're done the time complexity for this algorithm will be again big o of n
144
because we're going to define this array and go through this array only once
145
Okay, so that's how dynamic programming works
146
But now I'm gonna show you a quick demo with Python
147
and something called Jupyter Notebook to show you how this idea might play out in practice
148
So in this Jupyter Notebook, I have defined a few functions in Python Fib of n which is a recursive naive recursive solution and
149
Fib of memo and fib of 2 which represent a memoized solution and 5th bottom -up, which is of course a bottom -up solution.
150
So let's see how they compare to each other in performance
151
We're gonna try running fib of n first the naive recursive solution with fib of 5 and
152
That gives us 5 which is expected.
153
What about fib of 20?
154
That gives us the answer pretty quickly, too.
155
And what about fib of 35?
156
This actually takes 5 to 6 seconds on my computer
157
So it's obviously not the most efficient approach.
158
Let's see how fib of two and fib of memo the memoized solution compares to that
159
Let's try running fifth memo of five firsts and that gives us five which is expected
160
And what about fifth memo 35?
161
That's pretty quick, too.
162
And what about fifth memo 100 and 1000
163
This actually gives us an error and this error is called the recursion error
164
Python gives us this error actually because there are too many recursive calls on a call stack and
165
To fix that we can just use the bottom -up approach
166
One advantage of using a bottom -up approach is that we don't have to put any recursive calls on a call stack
167
So we don't have to worry about that.
168
So we're going to load this function and then run it with the argument 35
169
Which is pretty quick 1000 and then let's try 10 ,000 as well
170
And that's pretty instantaneous, too.
171
Okay, so that's my introduction to dynamic programming.
172
Let me know in the comment section below what you thought of this video,
173
and if you have any requests about what kind of videos I should make in the future,
174
let me know in the comment section below as well.
175
I'm YK from CSDojo, and I'll see you in the next video.
同频道
FOR YOU
推荐视频
本课的词汇与口语要点
这节口语课以视频“What Is Dynamic Programming and How To Use It”为素材。 视频中反复出现的词有:fib, return, Fibonacci, value, function。 这段视频共有 175 个句子、2286 个单词可供跟读。 讲话部分时长为 14:27。 说话人语速自然,每分钟约 158 个词,接近日常对话。 85% 的单词属于英语最常用的 3,000 词,其余的词建议在练习前先学一下。
视频中的重点词汇
视频中 15 个值得学习的单词,附发音和释义:
| 单词 | 发音 | 释义 |
|---|---|---|
| memo 名词 | /ˈmɛməʊ̯/ | 備忘錄 /备忘录, 便箋 /便笺 |
| sequence 名词 | /ˈsiː.kwəns/ | 序列, 順序 /顺序 |
| define 动词 | /dɪˈfaɪn/ | 界定 |
| execute 动词 | /ˈɛksɪˌkjuːt/ | 處決 /处决, 處死 /处死 |
| solve 动词 | /sɒlv/ | 解決 /解决 |
| algorithm 名词 | /ˈælɡəɹɪðm̩/ | 算法, 演算法 |
| bracket 名词 | /ˈbɹækɪt/ | 支架, 托架 |
| null 名词 | /nʌl/ | 空值 |
| element 名词 | /ˈɛləmənt/ | 要素 |
| compare 动词 | /kəmˈpɛɚ/ | 比, 比較 /比较 |
| efficient 形容词 | /ɪˈfɪʃənt/ | 高效率 |
| examine 动词 | /ɪɡˈzæmɪn/ | 检查, 调查 |
| stack 名词 | /stæk/ | 堆 |
| intermediate 形容词 | /ɪn.tə(ɹ)ˈmi.di.ət/ | 中間 /中间, 中級 /中级 |
| complexity 名词 | /kəmˈplɛk.sɪ.ti/ | 複雜性 /复杂性 |
视频中出现的短语动词
| 单词 | 释义 |
|---|---|
| come up with 动词 | 想出, 提出 |
| go down 动词 | 下降, 下去 |
| go through 动词 | 通過 /通过 |
视频中的语法
说话人最常用的结构,并附上视频中的原话:
| 结构 | 视频中的用法 |
|---|---|
| 被动语态 be + 过去分词 — 强调发生了什么,而不是谁做的 | is computed · is also called · is called |
| 现在完成时 have/has + 过去分词 — 过去发生但与现在仍有关联的事 | I've made · we've already seen · We've already stored |
| 定语从句 who / which + 从句 — 补充说明人或事物 | number, which is · operation, which is · five which is |
需要注意的发音
说话人用了 62 次缩略和弱读形式,例如 we're, don't, we'll。请按听到的简短形式来说。
- “sh” 和 “zh” 音: efficient /ɪˈfɪʃənt/, computation /ˌkɑmpjʊˈteɪʃn̩/, recursion /ɹɪˈkɜː(ɹ)ʒən/, memoization /ˌmɛmoʊaɪˈzeɪʃən/, exponentially /ɛkspə(ʊ)ˈnɛnʃəli/
- 长单词——注意重音位置: intermediate /ɪn.tə(ɹ)ˈmi.di.ət/, complexity /kəmˈplɛk.sɪ.ti/, temporary /ˈtɛmp(əˌɹ)ɛɹi/, repetitive /ɹɪˈpɛtɪtɪv/, memoization /ˌmɛmoʊaɪˈzeɪʃən/
中文母语者容易读错的音:
- /v/ — 不要读成 /w/,上齿轻触下唇: solve /sɒlv/, naive /naɪˈiv/, variable [ˈvæɹ.i.ə.bl̩], repetitive /ɹɪˈpɛtɪtɪv/, recursive /ɹɪˈkɜː(ɹ)sɪv/
- 词尾辅音 — 要读清楚,后面不要加元音: dynamic /daɪˈnæm.ɪk/, sequence /ˈsiː.kwəns/, execute /ˈɛksɪˌkjuːt/, solve /sɒlv/, bracket /ˈbɹækɪt/
- /r/ 和 /l/ 的区别: algorithm /ˈælɡəɹɪðm̩/, roughly /ˈɹʌf.li/, variable [ˈvæɹ.i.ə.bl̩]
如何用这段视频练习
- 先完整听一遍视频,不要开口,记下不认识的单词。
- 先用 0.75 倍速逐句跟读,熟练之后再回到正常速度。
- 录下自己的声音并与原声对比,特别注意 memo, sequence, define 这类单词。
什么是跟读法?
跟读法 (Shadowing) 是一种有科学依据的语言学习技巧,最初开发用于专业口译员的培训,并由多语言者Alexander Arguelles博士普及。这个方法简单而强大:您在听英语母语原声的同时立即大声重复——就像是一个延迟1-2秒紧跟说话者的影子。与被动听力或语法练习不同,跟读法强迫您的大脑和口腔肌肉同时处理并模仿真实的讲话模式。研究表明它能显着提高发音准确性,语调,节奏,连读,听力理解和口语流利度——使其成为雅思口语备考和真实英语交流最有效的方法之一。













