跟讀練習: 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秒緊跟說話者的影子。與被動聽力或語法練習不同,跟讀法強迫您的大腦和口腔肌肉同時處理並模模擬實的講話模式。研究表明它能顯著提高發音準確性,語調,節奏,連讀,聽力理解和口語流利度——使其成為雅思口語備考和真實英語交流最有效的方法之一。













