文档介绍：By:City
动态规划入门
Dynamic Programming
装配线问题
一个工厂共有两条装配生产线,每一条装配线上有n个装配站,编号为j = 0, 1, …, n – 1(n<=100000)。装配线i(i = 0或1),在装配站S[i][j]上所需的装配时间记为a[i][j]。一个汽车底盘进入工厂,然后进入装配线i的进入时间为e[i],在通过一条线的第 j个装配站后,这个底盘来到任一条线的第(j + 1)个装配站。如果留在相同的装配线上,则没有移动的开销;如果在装配站S[i][j]后,它移动到了另一条线上,则花费时间t[i][j]。求汽车通过每一个装配点所需要的最少时间,装配点顺序不能被打乱。
动态规划应用
动态规划通常应用于最优化问题。此类问题可以有多个可行解,最有情况可以用一个值表示,
动态规划是一种思想,应用非常广泛
很多著名算法实际上都是应用了动态规划的思想,
比如:Dij,霍夫曼树,背包问题等等
DP经常与DFS或递归结合使用
动态规划的目的在于通过记忆化的方式,减少对重复或无意义子问题的求解,进而大幅度提高算法的时间效率,代价是付出一定存储空间。
关于记忆化
把求解过程中遇到的子问题记录下来,防止下次需要时的重复计算
或者说对问题的状态进行记录
在线打表(递推公式)
Poj2696 A Mysterious Function
记忆化搜索
Poj1088
Description
给定一个二维数组,寻找一条从数组中某点开始到另一点结束的最长下降序列
数据范围:二维数组100*100
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
记忆化搜索
如果用dp[i][j]表示从(i,j)开始的一条最长路线,
Dp[i][j]=
max( dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])
方程前提是什么?代码应该怎样处理?
几种经典DP
最长不下降子序列
pku1887(最长上升子序列)
状态转移方程: Max(1)=1; Max( i )=Max{ Max(j):  1<=j<i && a[i]<a[j]   }+1;
注意有O(n*log(n))算法
mon Subsequence
Pku1458
设有二维数组 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1) f[i][j] = max{f[i − 1][j − 1] + same(i,j),f[i − 1][j],f[i][j − 1]} 其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”,否则为“0”。 此时,f[i][j]中最大的数便是 X 和 Y 的最长公共子序列的长度
扩展
Poj mon Increasing Subsequence