动态规划入门

伟大的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