伟大的acm大神谷哥教我学算法.
引例
斐波那契数
定义一个函数，f(x) = f(x-1) + f(x-2)，x为正整数，定义f(1) = 1，f(2) = 1。给出整数n，求f(n)的数值。
直观的做法：
int f(int n)
{
if(n==1||n==2)
return 1;
return f(n-1)+f(n-2);
}
思考:如果n为10^7程序还可以运行下去吗？（这里不考虑数据会爆int的问题）
显然效率低下.如下图所示:
beibo
我们可以看到计算f(n)的过程中有很多重复的计算。
这种做法的复杂度是指数级增长的！
进行优化,保存子状态，避免重复计算.
int f(int n){
vector<int>F(n+1,0);
F[1]=F[2]=1;
for(int i=3;i<n;i++){
F[i]=F[i-1]+F[i-2];
}
return F[n];
}
背包问题
有n个价值和体积分别为wi和vi的物品。从这些物品中挑选出总体积不超过V的物品，求所有方案中价值总和的最大值。
条件：
1≤ n ≤ 100
1≤ wi，vi ≤ 100
1 ≤ V ≤ 10000
wi，vi, V 均为整数
首先想到的是朴素递归:
rec(0,v)
int rec(int index,int capacity){
if(index==n) return 0;
else if(capacity<v[index]){
return rec(index+1,capacity);
}
else{
return max(rec(index+1,capacity),
rec(index+1,capacity-v[index])+w[index])
}
}
思考:深搜的深度是n每一次搜索需要两个分支时间复杂度是O（2^n）n很大了之后怎么办？
来看一下rec函数的递归计算情况
例如:n=4,(w,v)={(3,2),(2,1),(4,3),(2,2)},V=5
rec
以上问题都存在着冗余重复的计算,每个都能划分成子问题解决.
DP
思想及概念
基本思想：一般求解最优化问题。将求解问题分解成若干个子问题，保存已解决的子问题的答案，在需要的时候直接利用。
特点：子问题重叠
子问题的重叠能更好地显示出动态规划的优势。因此可以打表记录子问题的答案。
性质：
- 最优子结构：一个最优策略的子策略也是最优的。
- 无后效性：过去的步骤只能通过当前的状态影响未来的发展，当前状态是历史的总结。
动态规划不是一种算法，而是一种思想，应用于有动态决策的问题当中。
动态规划的状态是人为定义的。
一般步骤：
- 通过穷举计算过程图确定问题状态
- 列出状态转移方程（决策）
- 初始化和边界条件
- 优化
LCS(最长公共子序列)
问题描述:给定两个字符串S，T(长度小于1000)。求出这两个字符串最长的公共子序列的长度。
思考举例:
lcs
对于X和Y，我们试着计算X[1:i]与Y[1:j]的最长公共子序列。
lcs2
因此， 我们可以得到递推方程：
lcs3
dp[i][j]为序列 (X1, X2, …, Xi)和 (Y1, Y2, …, Yj)的最长公共子序列的长度。
LIS(最长上升子序列)
给出一个由n个数字成的序列A[1:n]，找出它的最长单调上升子序列。即求最大的m
使得a1<a2<…<am且A[a1]<A[a2]<…<A[am]
思考：先举出个例子 A[1:9] = 2 1 5 3 6 4 8 9 7。我们首先考虑A[1:i]的LIS，
令A[1:i]的LIS为dp[i].比如i=6,这时候A[i] = 4, 我们往i左边看。
lis
从上边的规律我们可以写出状态转移方程：
lis2
思考:这个算法的复杂度为O(N^2),还能做的更快吗?
对于这个例子 A[1:9] = 2 1 5 3 6 4 8 9 7
当i=6时，我们已经算出dp[3] = dp[4] = 2
其中j = 3,对应的序列为 {1, 5}
j = 4，对应的序列为 {1, 3}
其实我们更倾向要{1, 3},因为对于dp值为 2的情况A[j]越小,越有潜力被利用上进行更新。
因此我们重新开一个数组g,保存dp值为k的对应的数组A中的最小值。因此当i=6时,
g数组中有两个值,即g[1]=1,g[2]=3。
在计算dp[6]的时候只要用g数组中的值更新就好。
数组g，保存dp值为k的对应的数组A中的最小值。
g[1]<=g[2]<=……<=g[k]
计算dp[i]: 在g中找到大于等于A[i]的第一个数j, 则dp[i] = j更新g: 由于g[j]>A[i],则需要更新g[j] = A[i].
file(g,g+n,INFINITY);
for(int i=0;i<n;i++){
int j=lower_bound(g,g+n,A[i])-g;
dp[i]=j+1;
g[j]=A[i];
}
由于g是有序的，查找利用二分查找。总体复杂度为 O(n logn)
背包问题0/1
有n个价值和体积分别为wi和vi的物品。从这些物品中挑选出总体积不超过V的物品，求所有方案中价值总和的最大值。
条件：
1≤ n ≤ 100
1≤ wi，vi ≤ 100
1 ≤ V ≤ 10000
wi，vi, V 均为整数
观察这个题目的特点：
- V不超过10000
- 整数
引例中朴素方法有很多重复计算。
引例中的状态是2维的(前index个背包，剩下容积)
引入dp[i][j]，表示前i个物品中用了容积j获得的最大价值。
递归方程为:
beibao01
复杂度为O(n*V)
总结
动态规划是一种思想。动态规划有很多类型（如普通DP, 树形DP，状压DP，按位DP，插头DP等）；
动态规划思想的养成不可能一蹴而就，而是慢慢养成的。养成的过程需要不断增加题目的见识面，不能局限于几种类型的DP；
学好DP需要下很大功夫。同样的, 学好DP，会对个人算法素养提升很大。而且，DP也是面试中常见的考点
参考:
《算法竞赛入门经典》…………刘汝佳 等
《ACM竞赛基础教程》………...俞经善 等
《编程之法》……………………July
http://blog.csdn.net/zsc09_leaf/article/details/6536802
http://poj.org/problem?id=1458
http://poj.org/problem?id=3254
http://blog.csdn.net/y990041769/article/details/24658419
网友评论