动态规划：

动态规划的基本思想是，把大问题拆解成子问题（这一点和分治法一样），先求解子问题，然后通过子问题求出原问题。

与分治法不同，子问题并不独立。可以记录子问题然后快速解决后续相同的子问题。

采用动态规划算法，子问题必须重复出现，且具备最优子结构和重叠子问题性质。

动态规划会填表记录，有如下步骤：

动态规划的斐波那契数列问题：

Fib(n)

{

if n == 0 return 0

if n == 1 return 1

dp[0] ← 0

dp[1] ← 1

for i = 2 to n do

dp[i] ← dp[i-1] + dp[i-2]

return dp[n]

}

这是动态规划算法

Fib(n)

{

if n == 0 return 0

if n == 1 return 1

return Fib(n-1) + Fib(n-2)

}

这是直接递归

不难看出，动态规划储存了每个解，计算速度更快，但有额外的储存占用。

求最长子序列问题

图算法