动态规划(Dynamic Programming)
1. 什么是动态规划？
Fibonacci序列 Fibonacci序列被定义如下： F(n) = F(n - 1) + F(n - 2), n≥ 3 问题：如何计算第n个Fibonacci数F(n)?
算法1 F(1) = 1 F(2) = 1 F(n) = F(n - 1) + F(n - 2), n≥ 3 F(n) if (n == 1) return 1; if (n == 2) return F(n - 1) + F(n - 2);
算法1的效率 F(n) if (n == 1) return 1; if (n == 2) return F(n - 1) + F(n - 2);
算法1的效率 F(n) if (n == 1) return 1; if (n == 2) return F(n - 1) + F(n - 2); 目标：计算F(100)。 问题：在计算F(100)的过程中， F(99)被调用(计算)多少次？ F(98)被计算多少次? … … F(3)被计算多少次?
F(100)的执行过程 … …
算法2 F(n) Fib[1] = 1; Fib[2] = 1; for i = 3 to n Fib[i] = Fib[i – 1] + Fib[i – 2]; return Fib[n]; Fib[1..n]是一维数组, 用Fib[i]来存储F(i)的值。
算法1 vs 算法2
什么是动态规划？ 对于有些问题，解决该问题的过程中需要重复解决该问题的子问题。 动态规划是一种解决此类问题的方法。其核心思想是：“重用子问题的计算结果，避免重复计算”。