第五章 动态规划
第五章 动态规划1、dfs与影象化搜刮
重复搜刮问题
在递归算法中，重复搜刮指的是在解决问题的过程中反复计算相同的子问题，导致服从低下的问题。
特殊是在具有重叠子问题的场景下，重复搜刮会极大地增加算法的时间复杂度。
斐波那契数列F(n) ＝F(n一1) +F(n一2) 的简朴递归解法会导致大量的重复计算。详细体现如下：
[*]计算 F(5) 时管帐算F(4) + F(3)。
[*]计算F(4) 时又管帐算F(3) +F(2)，此中F(3)被多次重复计算。
[*]每个节点的子问题需要重新计算，从而导致指数级增长。
[*]
这种情况在许多递归算法中都会出现。
影象化搜刮的实现
影象化搜刮是在递归的基础上增加了一个记录中间效果的缓存（一般是数组），制止重复计算。
https://i-blog.csdnimg.cn/direct/5bd751fa6dac4101ba8c77dd1c171bc0.png
斐波拉契序列影象化搜刮的代码
static int f(int n){
if(n==1||n==2) return 1;
if(f!=-1) return f;
return f=f(n-1)+f(n-2);
}
页:
[1]