前言

这一强大的算法却有一个不相关的名字，常常引起混淆。实际上创造者Richard Bellman把这名字作为保护伞来掩人耳目的，从此延续下来。说它强大是因为应用范围很广，在优化算法中，在图像融合中，在很多实际问题中都有其身影。还因为使用它往往能收到奇效，当你尝试了分治，尝试了贪心仍然不能满意的时候也许动态规划才是最好的选择。这么好的方法想从心所欲并非易事，甚至很多时候无从下手。像动态规划算法本身所做的那样，我们把大事化小，小事化了，循序渐进的掌握它。

动态规划三部曲

• 大问题分解成子问题
• 从子问题分析状态和状态转移方程
• 自底向上的实现

和分治一样的地方是把大的化小，不一样的是在动态规划中小问题与原问题的本质相同，并且小问题的规模减少的不多，不是分治期望的一半。这样一来如果应用分治算法会大量的计算重复子问题导致十分缓慢，在动态规划中把这些小问题的结果存储下来不断的调用，这也是为什么要自底向上实现的原因。难就难在了第二部分，怎样分析出状态和状态转移方程，让我们结合具体的例子来理解。

动态规划4例

1. 凑硬币????说我们有面值为1,3,5的硬币若干，问凑够11元所需最少硬币数。

三部曲之一，大化小。假如把凑够11元看成一个大问题，那么小问题是什么？凑够10元？9元？。。。或者说凑够i元。小问题浮出水面，凑够i元所需最少硬币就是原问题的子问题，这一子问题与原问题是同质的。换一个角度来看，如果这个子问题你解决了，那么原问题或者和原问题相当的问题你都解决了，说白了你解决的是一类问题。什么凑够888元，999元都不在话下。

三部曲之二，由子问题到状态和状态转移方程。状态就是子问题的数学表达，借助于数学符号易于发现其中规律。d[i]=j，表示凑够i元最少需要j个硬币。那么好了，从最简单的情况开始，通过归纳和对比看看能不能找出什么规律来。d[0]=?，换句话说凑够0最少需要多少硬币，当然是0个了，所以d[0]=0。也不难发现d[1]=d[1-1]+1=1，d[2]=d[2-1]+1=2。d[3]的时候就有所不同了，当然我们都知道d[3]=1，就是凑够3最少需要1个硬币。那么这个1是怎么来的？放慢思维会发现，首先试图用面值1元的需要3个，然后用面值3元的需要1个，面值5元的我们智慧大脑果断放弃了。在照顾到所有情况以后，得到结果d[3]=min(d[3-1]+1,d[3-3]+1)=1。把d[0]，d[1]，d[2]，d[3]写成更一般的形式d[i]=min(d[i-v[j]]+1)，i>v[j]（j表示第j个硬币，v[j]表示第j个硬币的面值）。d[i]=min(d[i-v[j]]+1)，i>v[j]就是状态转移方程，描述状态之间的转化关系。

三部曲之三，自底向下实现，有了状态和状态转移方程实现顺其自然，需要留意的地方是初始状态，它是已知的，通常是0或者无穷大，或者无穷小。

/**1.凑硬币

输入：现有面值1,3,5,7 的硬币若干

输出：如何用最少的硬币凑够S元，比如说11元。

状态：d[i]表示凑够i所用的最少硬币

状态转移方程：d[i] =min(d[i-v[j]]+1), v[j]<=i (v[j]表示第j个硬币的面值)

*/

void coin_assmbling()

{

const int Money = 11;

vector<int> value = {1,3,5,7};

vector<int> d(Money + 1, Infinity);

d[0] = 0;

for (int i = 1; i < Money + 1; ++i)

for (int j = 0; j < value.size();++j)

{

if (value[j] <= i && d[i] > d[i - value[j]] + 1)

{

d[i] = d[i - value[j]] + 1;

}

}

cout << "min coin num: " << d[Money] << endl;

}

?

1. 最长非降子序列的长度????[5，3，4，8，6，7]的最长非降子序列是3，4，6，7长度是4

还是原来的步骤，还是原来的方法。子问题？[5，3，4，8，6]是原序列的子序列，[5，3，4，8]也是。那么用A[i]
表示以第i个元素结尾的序列，A[i]的最长非降子序列就是原问题的一个子问题。求出所有A[i]的最长非降子序列，其中最最长的就是最终的结果。用d[i]表示以第i个元素结尾的最长非降子序列，从易到难。

• 前一个数的LIS：d[1]=1（序列5）
• 前两个数的LIS：d[2]=1（序列5，3，3前面没有比3小的）
• 前三个数的LIS：d[3]=2（序列5，3，4；4前有3所以d[3]=d[2]+1）
• 前4个数的LIS：d[4]=3（序列5，3，4，8；d[4]=max(d[1],d[2],d[3]+1)）

有上面分析得到状态转移方程d[i]=max(1，d[j]+1) j<i，a[j]<=a[i]。文字表述就是把i前面的各个子序列中，最后一个不大于a[i]的数加1，其中的最大值就是所求。当然有可能每个子序列都大于a[i]，比如[5，4，3，2，1]的最长非降子序列是1。

/**2.最长非降子序列（LIS）

输入：数组 a

输出：最长非降子序列的长度及其内容

状态：d[i]表示以a[i]结尾的最长非降子序列的长度

状态转移方程：d[i]={max(1,d[j+1]), j<i a[j]<=a[i]}

*/

void longest_increasing_subsequence()

{

vector<int> a = { -2, 11, -4, 13, -5, -2 };

vector<int> d(a.size(), 1);

d[0] = 1;

int max = d[0];

int max_id = 0;

for (int i = 1; i < a.size();++i)

{

for (int j = 0; j < i;++j)

{

if (a[j] <= a[i] && d[i] < d[j] + 1)

d[i] = d[j] + 1;

}

if (max < d[i])

{

max = d[i];

max_id = i;

}

}

// print max length

cout << "max length is: " << max << endl;

// print subsequence element

cout << "they are: " << endl;

cout << a[max_id] << "\t";

int temp = max;

for (int i = max_id-1; i >= 0;--i)

{

if (d[i] == temp - 1)

{

cout << a[i] << "\t";

temp -= 1;

}

}

cout << endl;

}

?

1. 最长公共子序列????比如度量两个DNA序列的相似程度。

这比上面的例子更复杂，它是2维的动态规划问题。因为需要两个变量来刻画状态。还是先找出子问题。考虑到两个序列的子序列可以分别表示成A[i]和B[j]，自然联想d[i][j]表示以i结尾的序列A[i]和以j结尾的序列B[j]他们最长公共子序列的长度。考虑d[i][j]和它前面状态d[i-1][j]，d[i][j-1]，d[i-1][j-1]之间的关系。容易得到状态转移方程

d[i][j]={0，i==0||j==0; d[i-1][j-1]+1，a[i]==b[j]; max(d[i-1][j],d[i][j-1])，a[]!=b[j];}

/**3.最长公共子序列（LCS）

输入：两个数组 a b

输出：求他们的最长公共子序列

分析：1.首先把大问题变成小问题，把原问题转化成求两个不完全数组的公共子序列，求以分别以a[i]和b[j]结尾的子数组的最长公共子序列。

2.从子问题分析状态，s[i][j]表示a[i] b[j]结尾的子数组的最长公共子序列。进一步分析前一状态和后一状态之间的关系。

状态：s[i][j]

状态转移方程：d[i][j]={0 i==0|| j==0; d[i-1][j-1]+1 a[i]==b[j]; max(d[i-1][j],d[i][j-1], a[i]!=b[j]);}

*/

void longest_common_subsequence()

{

const string a = { ‘A‘, ‘B‘, ‘C‘, ‘B‘, ‘D‘, ‘A‘, ‘B‘ };

const string b = { ‘B‘, ‘D‘, ‘C‘, ‘B‘, ‘A‘ };

?

vector<vector<int>> d(a.size()+1);

for (auto& e:d)

{

e.resize(b.size()+1);

}

vector<vector<int>> table(d);

?

for (int i =0 ; i < a.size();++i)

{

for (int j = 0; j < b.size();++j)

{

if (a[i] == b[j])

{

d[i + 1][j + 1] = d[i][j]+1;

table[i + 1][j + 1] = 0;

}

else if (d[i][j + 1]>d[i + 1][j])

{

d[i + 1][j + 1] = d[i][j + 1];

table[i + 1][j + 1] = 1;

?

}

else

{

d[i + 1][j + 1] = d[i+1][j];

table[i + 1][j + 1] = 2;

}

}

}

cout << "longest common subsequence: " << d[a.size()][b.size()]<<endl;

cout << "they are: " << endl;

int r = a.size();

int c = b.size();

?

for (int i = a.size()-1; i>=0; --i)

{

if (table[r][c] == 0)

{

cout << a[r - 1] << "\t";

r -= 1;

c -= 1;

}

else if (table[r][c] == 1)

{

r -= 1;

}

else

{

c -= 1;

}

}

cout << endl;

}

?

1. 0-1背包问题

/**4.0-1背包

输入：一个容量V的背包，若干宝石，价值体积各不同。

输出：可能装入宝石的最大价值

分析：这是一种有限制条件的动态规划问题，因此通常需要一个额外的状态来刻画限制条件。

1.首先把大问题转化成小问题，假设s[i]代表加入前个宝石能达到的最大价值。这并没有体现背包容量的限制。

因此使用s[i][j]表示把前i个宝石装入到剩余体积j的背包中能达到的最大价值。

2.由状态分析状态转移方程，思考d[i][j]与d[i-1]的关系。显然两种情况，既是装入和不装入第i件物品。

状态：d[i][j]把前i个宝石装入到剩余体积j的背包里能达到的最大价值

状态转移方程：d[i][j]=max(d[i-1][j-vo[i]]+va[i], d[i-1][j])

*/

void knapsack()

{

const int V = 12;

vector<int> value = { 10, 9, 6, 1, 4, 9, 20, 6, 20, 4 };

vector<int> volume = { 5, 4, 3, 5, 2, 6, 4, 4, 3, 4 };

vector<vector<int>> d(value.size()+1);

for (auto& e:d)

{

e.resize(V+1);

}

?

int j = V;

for (int i = 0; i < value.size();++i)

{

for (int j = 0; j < V; ++j)

{

d[i + 1][j + 1] = d[i][j + 1];

if (j>=volume[i] && d[i + 1][j + 1] < d[i][j + 1 - volume[i]] + value[i])

d[i + 1][j + 1] = d[i][j + 1 - volume[i]] + value[i];

}

}

?

cout << "max value: " << d[value.size()][V] << endl;

cout << "they are: " << endl;

?

//vector<int> table(value.size());

j = V;

for (int i = value.size()-1; i >= 0; --i)

{

if (d[i + 1][j] > d[i][j])

{

cout << value[i] << "\t";

j -= volume[i];

}

}

cout << endl;

}

?

参考

http://hawstein.com/posts/dp-novice-to-advanced.html

http://blog.csdn.net/zmazon/article/details/8247015