记忆化搜索dp的三种实现方式

1、动态规划的理论基础最优性原理最优性原理: 若最短路uv经过中间结点w, 则uw和wv的路径分别是u到w和w到v的最短路.uvw最优性原理的应用：动态规划设F(d)为A到D的最短路长度要从A走到D，最后一步有以下三种方案1:经过c1到d，由最优性原理，最短路f(c1)+42:经过c2到d，由最优性原理，最短路f(c2)+33:经过c3到d，由最优性原理，最短路f(c3)+5上一阶段的状态下一阶段的状态决策动态规划通用方程Fi:从初始状态0走到i的最优值（最短路）递推式：Fi=minfi+disti,i (i是i的上一步,disti,i是i到i的距离)边界：F0=0因此只要依次确定f0,f1,f2

2、就可以了动态规划的实现方式1：朴素算法（松驰操作）2：记忆化搜索3：递推松驰操作要点动态规划与最短路动态规划求初始状态0到所有节点的最短路长度松驰操作：Fi:从初始状态0到状态i的最优值紧边：使从0到i更优的边。（使fi更优）设0到i有一根绳，我们可以通过减小Fi的值，从而使这根绳变松。If fj+w(j,i)fi then fi:=fj+w(j,i)用紧边w(j,i)对状态i进行松驰操作使fi更优结论存在紧边，一定没有正确的求出最短路树不存在紧边，一定正确的求出最短路树动态规划的朴素算法松驰操作理解：松驰操作的结果是使fi减小到最小（无紧边）。实现：初始化F0=0,fi=max只要存在紧边，

3、则用紧边对节点进行松驰操作，直到无紧边为止。思考：是不是所有的动态规划都可以用这个方法实现？为什么我们看到的大部分动态规划程序没有采用这个方法，而是使用递推来实现呢？朴素算法与递推算法的效率程序结构1、初始化：F0=0;fi=max2、松驰操作：flag:=有紧边while flag=有紧边 dobegin flag:=无紧边; 枚举i; 再枚举i的所有入边w(j,i); if fj+w(j,i)fi then begin fi:=fj+w(j,i); flag:=有紧边; end;end;时间复杂度：O(x*节点总数*入度) (x待定)递推程序结构1、初始化：F0=0;fi=max2、松驰操

4、作：按一定的顺序依次枚举i;再枚举i的所有入边w(j,i);if fj+w(j,i)fi thenbegin fi:=fj+w(j,i); flag:=有紧边; end;时间复杂度：O(节点总数*入度) 该算法一个重要前提条件:在枚举i的所有入边w(j,i)时，必须保证fj最优值已确定！该算法效率高的主要原因：只枚举i的所有入边。记忆化搜索递推的效率很高但有时阶段不容易找，或不容易递推怎么办记忆化搜索Var f:array0.nof integer;/保存状态i的最优值Fi先初始化为极小值(0 then exit(fi); for 枚举i的所有入边j 如果从0-j-i的代价比fi更优，更新fi exit(fi);End;石子合并有n个数a1,a2a