文档介绍：动态规划1
罗方炜
简介
DP是在20世纪50年代由一位卓越的美国数学家Richcard Bellman发明的。它作为一种重要的工具在应用数学中被广泛的应用。它不仅可以解决特定类型的优化问题,还可以作为一种通用的算法设计技术来使用。
DP的实质
利用问题的所具有的重叠子问题的性质进行记忆化求解。(用空间换时间)
i数:
f(n) = f(n-1) + f(n-2) n>2
f(1)=f(2)=1
常规递归
int Non_DP(int n)
{   if (n==1 || n==2)     return 1;   else     return Non_DP(n-1) + Non_DP(n-2); }
指数级时间复杂度,无法忍受
两种实现方式
自底向上(bottom up)
int DP_Bottom_Up(int n)
{   memo[1] = memo[2] = 1;
for (int i=3; i<=n; i++)
memo[i] = memo[i-1] + memo[i-2];
return memo[n]; }
自顶向下(top down)
int DP_Top_Down(int n)
{ if (n == 1 || n == 2) return 1;
if (memo[n] != 0) return memo[n];
memo[n] = DP_Top_Down(n-1) + DP_Top_Down(n-2);
return memo[n]; }
基本概念
最短路问题
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E
求A到E的最短路径。
直观的方法是用回溯法搜索。时间复杂度为指数级。
低效的原因:没有充分利用重叠子问题的性质。
此图有明显的次序,可以划分为5阶段。
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E
阶段0
阶段1
阶段2
阶段3
阶段4