1先看调用装饰器函数解决一个斐波那契求和的问题
2def memo(f):
3 cache = {}
4 def memorized(n):
5 if n not in cache:
6 cache[n] = f(n)
7 return cache[n]
8 return memorized
9
10@memo
11def fib(n):
12 if n == 0 or n == 1:
13 return 1
14 return fib(n-1) + fib(n-2)
15
16def main():
17 T = int(input().strip())
18 for _ in range(T):
19 n = int(input().strip())
20 print(fib(n))
21
22动态规划 DP（入门）
23二、前提条件
24如果没有 cache：
25
26int fib(int n)
27{
28 if(n==0||n==1)
29 return 1;
30
31 return fib(n-1)+fib(n-2);
32}
33
34例如：fib(5)
35
36会变成：fib(5)
37
38├── fib(4)
39│ ├── fib(3)
40│ └── fib(2)
41│
42└── fib(3)
43 ├── fib(2)
44 └── fib(1)
45
46继续展开：
47
48fib(2)
49fib(3)
50fib(2)
51会被反复计算。
52
53三、什么叫重叠子问题
54
55观察上图：fib(3)出现两次。
56fib(2)出现三次。
57
58实际上：fib(20)
59里面：
60fib(18)
61fib(17)
62fib(16)
63...
64
65会被算无数次。
66
67这就是：重叠子问题
68定义：同一个子问题被重复求解。
69
70这是DP出现的第一个条件。
71
72四、 cache 干了什么
73
74第一次：fib(5)
75
76需要：fib(4)
77
78于是计算：fib(4)=5
79
80然后：cache[4]=5
81保存下来。
82
83以后再需要：fib(4)
84
85直接：return cache[4]
86
87不再递归。
88
89因此：
90每个 fib(k)
91只会真正计算一次
92
93五、用 C 语言模拟 cache
94
95 Python：
96
97cache[n]=f(n)
98
99在 C 里面可以写成：
100
101int cache[1000];
102
103初始化：
104
105for(int i=0;i<1000;i++)
106{
107 cache[i]=-1;
108}
109
110表示：
111-1
112代表没算过
113六、记忆化搜索
114定义缓存
115int cache[1000];
116递归
117int fib(int n)
118{
119 if(n==0||n==1)
120 return 1;
121
122 if(cache[n]!=-1)
123 return cache[n];
124
125 cache[n]=fib(n-1)+fib(n-2);
126
127 return cache[n];
128}
129或者
130int fib(int n)
131{
132 if(n==0||n==1)
133 {
134 return 1;
135 }
136
137 if(cache[n]==-1)
138 {
139 cache[n]=fib(n-1)+fib(n-2);
140 }
141
142 return cache[n];
143}
144模板就是这样：
145int dfs(...)
146{
147 if(边界)
148 return ...;
149
150 if(memo[状态]==-1)
151 {
152 memo[状态]=递归计算;
153 }
154
155 return memo[状态];
156}
157主要还是要保持状态，不太方便，更好的方式是拿DP数组
158七、执行过程
159
160例如：fib(5)
161
162第一次：cache[5]=-1
163
164说明没算过。
165
166于是：fib(4)+fib(3)
167
168算完后：cache[5]=8保存。
169
170以后再调用：
171
172fib(5)
173
174直接：return cache[5];
175
176结束。
177
178八、为什么这已经属于 DP
179
180很多教材会说：
181
182DP要写dp数组
183
184实际上不准确。
185
186写法：
187递归+缓存
188已经是DP。
189
190学术名字：
191Memoization
192记忆化搜索
193
194关系：
195
196暴力递归
197
198↓
199
200加缓存
201
202↓
203
204记忆化搜索
205
206↓
207
208动态规划
209九、DP到底在干什么
210实际上DP只干一件事：
211
212避免重复计算
213
214例如：fib(30)暴力递归：算几十万次
215
216记忆化搜索：
217
218fib(0)
219fib(1)
220...
221fib(30)
222
223每个只算一次。
224
225十、进一步观察
226代码里：
227
228fib(n)=fib(n-1)+fib(n-2)
229其实可以写成：
230
231dp[n]=dp[n-1]+dp[n-2]
232
233这里：fib(n)
234就是：状态 State
235
236所以：dp[i]
237表示第i项斐波那契数
238
239十一、状态转移方程
240
241DP最重要的东西：状态转移方程
242
243对于斐波那契：dp[i]=dp[i−1]+dp[i−2]
244
245意思：当前状态
246由之前状态推出来
247
248十二、为什么以后不用递归
249
250fib(100)
251
252会递归：100层
253
254虽然有cache。
255
256但还是有：函数调用开销
257
258于是可以直接写：
259
260dp[0]=1;
261dp[1]=1;
262
263然后：
264
265for(i=2;i<=n;i++)
266{
267 dp[i]=dp[i-1]+dp[i-2];
268}
269
270
先看调用装饰器函数解决一个斐波那契求和的问题
def memo(f):
cache = {}
def memorized(n):
if n not in cache:
cache[n] = f(n)
return cache[n]
return memorized
@memo
def fib(n):
if n == 0 or n == 1:
return 1
return fib(n-1) + fib(n-2)
def main():
T = int(input().strip())
for _ in range(T):
n = int(input().strip())
print(fib(n))
动态规划 DP（入门）
二、前提条件
如果没有 cache：
int fib(int n)
{
if(n==0||n==1)
return 1;
return fib(n-1)+fib(n-2);
}
例如：fib(5)
会变成：fib(5)
├── fib(4)
│ ├── fib(3)
│ └── fib(2)
│
└── fib(3)
├── fib(2)
└── fib(1)
继续展开：
fib(2)
fib(3)
fib(2)
会被反复计算。
三、什么叫重叠子问题
观察上图：fib(3)出现两次。
fib(2)出现三次。
实际上：fib(20)
里面：
fib(18)
fib(17)
fib(16)
...
会被算无数次。
这就是：重叠子问题
定义：同一个子问题被重复求解。
这是DP出现的第一个条件。
四、 cache 干了什么
第一次：fib(5)
需要：fib(4)
于是计算：fib(4)=5
然后：cache[4]=5
保存下来。
以后再需要：fib(4)
直接：return cache[4]
不再递归。
因此：
每个 fib(k)
只会真正计算一次
五、用 C 语言模拟 cache
Python：
cache[n]=f(n)
在 C 里面可以写成：
int cache[1000];
初始化：
for(int i=0;i<1000;i++)
{
cache[i]=-1;
}
表示：
-1
代表没算过
六、记忆化搜索
定义缓存
int cache[1000];
递归
int fib(int n)
{
if(n==0||n==1)
return 1;
if(cache[n]!=-1)
return cache[n];
cache[n]=fib(n-1)+fib(n-2);
return cache[n];
}
或者
int fib(int n)
{
if(n==0||n==1)
{
return 1;
}
if(cache[n]==-1)
{
cache[n]=fib(n-1)+fib(n-2);
}
return cache[n];
}
模板就是这样：
int dfs(...)
{
if(边界)
return ...;
if(memo[状态]==-1)
{
memo[状态]=递归计算;
}
return memo[状态];
}
主要还是要保持状态，不太方便，更好的方式是拿DP数组
七、执行过程
例如：fib(5)
第一次：cache[5]=-1
说明没算过。
于是：fib(4)+fib(3)
算完后：cache[5]=8保存。
以后再调用：
fib(5)
直接：return cache[5];
结束。
八、为什么这已经属于 DP
很多教材会说：
DP要写dp数组
实际上不准确。
写法：
递归+缓存
已经是DP。
学术名字：
Memoization
记忆化搜索
关系：
暴力递归
↓
加缓存
↓
记忆化搜索
↓
动态规划
九、DP到底在干什么
实际上DP只干一件事：
避免重复计算
例如：fib(30)暴力递归：算几十万次
记忆化搜索：
fib(0)
fib(1)
...
fib(30)
每个只算一次。
十、进一步观察
代码里：
fib(n)=fib(n-1)+fib(n-2)
其实可以写成：
dp[n]=dp[n-1]+dp[n-2]
这里：fib(n)
就是：状态 State
所以：dp[i]
表示第i项斐波那契数
十一、状态转移方程
DP最重要的东西：状态转移方程
对于斐波那契：dp[i]=dp[i−1]+dp[i−2]
意思：当前状态
由之前状态推出来
十二、为什么以后不用递归
fib(100)
会递归：100层
虽然有cache。
但还是有：函数调用开销
于是可以直接写：
dp[0]=1;
dp[1]=1;
然后：
for(i=2;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
