剑指Offer——动态规划算法
什么是动态规划？
和分治法一样，动态规划（dynamic programming）是通过组合子问题而解决整个问题的解。
分治法是将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解。
动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。
此时，分治法会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题时重新计算答案。
适用范围
最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。
最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。
1.问题中的状态满足最优性原理。
2.问题中的状态必须满足无后效性。
所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前状态是对以往决策的总结”。
动态规划算法的设计
两种方法：
自顶向下（又称记忆化搜索、备忘录）：基本上对应着递归函数实现，从大范围开始计算，要注意不断保存中间结果，避免重复计算
自底向上（递推）：从小范围递推计算到大范围
动态规划的重点
递归方程+边界条件
爬楼梯问题
一个人每次只能走一层楼梯或者两层楼梯，问走到第80层楼梯一共有多少种方法。
设DP[i]为走到第i层一共有多少种方法，那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2（走到第一层只有一种方法：就是走一层楼梯；走到第二层有两种方法：走两次一层楼梯或者走一次两层楼梯）。同理，走到第i层楼梯，可以从i-1层走一层，或者从i-2走两层。很容易得到：
递推公式：DP[i]=DP[i-1]+DP[i-2]
边界条件：DP[1]=1 DP[2]=2
(a)自顶向下的解法：
-
long long dp[81] = {0};/*用于保存中间结果否则会重复计算很多重复的子问题*/
-
long long DP(int n)
-
{
-
if(dp[n])
-
return dp[n];
-
if(n == 1)
-
return 1;
-
if(n == 2)
-
return 2;
-
dp[n] = DP(n-1) + DP(n-2);
-
return dp[n];
-
}
(b)自底向上的解法：
-
int i;
-
long long dp[81]; /* 注意当n超过75时，结果值将超过int范围 */
-
dp[1] = 1;
-
dp[2] = 2;
-
for(i=3; i <= 80; i++)
-
dp[i] = dp[i-1] + dp[i-2];
最长上升子序列
对于序列：4 1 2 24，它的最长上升子序列是1 2 4，长度为3。
对于序列：4 2 4 25 6，它的最长上升子序列是2 4 5 6，长度为4。
设a[i]表示原序列，设DP[i]表示以第i个数结尾的最长上升序列的长度，那么很显然想导出DP[i]的值，需要在DP[k](1<=k<i)中找出满足a[k]<a[i]最大的一项。假设第kk项是我们找到的答案，那么第i个数就可以接在第kk个数之后，成为以第i个数结尾的最长升序列。如果没有找到答案，换言之第i个数比前面的数都要小，那么DP[i]=1，也即生成了从自己开始又以自己结尾的最长升序列。综上，我们很容易得出：
递推公式：DP[i]=max(DP[k]+1,DP[i]) 1<=k<i
边界条件：DP[i]=1 1<=i<=n
算法复杂度为O(n^2)
-
void RiseSequence(int Array[], int num)
-
{
-
#define MAX_LENGTH 30
-
struct
-
{
-
int SequenceValue; /* max length ending with this num */
-
int PreviousIndex; /* record the previous number */
-
}ArrayInfo[MAX_LENGTH], temp;
-
int i;
-
for(i = 0; i < num; i++)
-
{
-
int j;
-
ArrayInfo[i].SequenceValue = 1;
-
ArrayInfo[i].PreviousIndex = -1;
-
for(j = 0; j < i; j++)
-
{
-
if(Array[j] < Array[i] && (ArrayInfo[j].SequenceValue + 1 > ArrayInfo[i].SequenceValue))
-
{
-
ArrayInfo[i].SequenceValue = ArrayInfo[j].SequenceValue + 1;
-
ArrayInfo[i].PreviousIndex = j;
-
}
-
}
-
}
-
temp.SequenceValue = ArrayInfo[0].SequenceValue;
-
for(i = 1; i < num; i++)
-
{
-
if(temp.SequenceValue < ArrayInfo[i].SequenceValue)
-
{
-
temp.SequenceValue = ArrayInfo[i].SequenceValue;
-
temp.PreviousIndex = i;
-
}
-
}
-
for(i = 0; i < temp.SequenceValue; i++)
-
{
-
printf("%d ", Array[temp.PreviousIndex]); /* in reverse order */
-
temp.PreviousIndex = ArrayInfo[temp.PreviousIndex].PreviousIndex;
-
}
-
printf("\nthe max rising sequence length is %d\n", temp.SequenceValue);
-
}
最长公共子序列
给定两个序列X和Y，称序列Z是X和Y的公共子序列如果Z既是X的一个子序列，又是Y的一个子序列。例如，如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列，但是它并不是X和Y的最长公共子序列，因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a}，长度为4，因为找不到长度为5或更大的公共子序列，所以X和Y的最长公共子序列长度就为4。
假设两个序列数组分别为a，b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况：
1.假如a[i]=b[j]，那么f(i,j)=f(i-1,j-1)+1
2.假如a[i]!=b[j]，那么f(i,j)=max(f(i-1,j),f(i,j-1))
边界条件为：f(i,0)=0 1<=i<=len(a)
f(0,j)=0 1<=j<=len(b)
算法复杂度：O(n^2)，len(a)表示数组a的长度。
尾声
动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题，去设计状态转移方程式。
动态规划还有很多变形，如状态压缩，树形等等。
虽然通常我们用递归的方式分析动态规划问题，但最终都会基于循环去编码。
美文美图
文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。
原文链接：shq5785.blog.csdn.net/article/details/52103965