动态规划简介：爱的初体验
动态规划是一个让人欲仙欲死、死去活来的科目，茫然无措时让你痛不欲生，柳暗花明时让你喜不自胜。
小伙，不能啊！
你要心怀有爱，你要用全身心的爱来迎接今天，迎接动态规划。
一、动态规划的概念
动态规划（dynamic programing）是利用子问题的解来解决整个问题的，这一点和分治法有些神似。
维基百科上说：
This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger subproblems by using the solutions to small subproblems. 这通常以表格形式完成，通过使用小子问题的解来迭代生成越来越大的子问题的解。
这指出了动态规划的两个特点：
①列表格（tabular form）：每个动态规划算法都从一个表格开始。
②以小解大：利用较小问题的解（using the solutions to small subproblems）去求较大问题的解（generating solutions to bigger and bigger subproblems），这样不停地迭代（iteratively）。小问题为什么能解大问题呢，这说明这些子问题之间是相互关联的。
就像砌墙一样，表格里的每个单元格就像一块块砖头，把所有砖头垒完，墙也就砌完了。同样，填满所有格子，也就得到了问题的答案。这就是动态规划的整个过程。
二、动态规划的优势
动态规划和分治法同样利用子问题来求解，但解题思路却是完全相反的。
分治法是从要求解的问题出发，将问题一层层划分成相对独立的子问题，递归地解决所有子问题，然后再合并子问题，最终解决原问题。从名字也可以看出，分治法的核心在于分解，就像分家一样，把问题打散了求解。它是自上而下的。
在这个分开求解的过程中，会做很多无用功，即重复地求解同样的子问题。比如有一个敲村里所有寡妇门的问题，村里有一个王寡妇特别招人烦，你要敲任何一个寡妇的门她就会说：“老娘没空，去敲王寡妇的门”。于是，如果你用分治法解决这道题，王寡妇家的门就被敲爆了。
动态规划的思路与分治法正相反，它是自下而上的，从最小的子问题开始，对每个子问题只求解一遍，并且将其结果保存在表中，下次用到时直接从表中取出来就行了，从而避免了子问题的重复计算。
这么看来，动态规划也没什么高深的，不就是列表格、查表格吗？
别说，还真就是这么回事。
只不过，真遇到问题，你就算吃出吃奶的劲儿，不，即便使出宇宙洪荒之力，也未必能列出这个表格。
山无棱、天地合，你也未必能列出这表格。
三、适用范围
动态规划常用于最优化问题，这类问题要求在给定的约束条件下找到最优解。
1．适用的主要问题类型
(1)图论问题
动态规划在图论中有广泛的应用，如最短路径问题（Bellman-Ford算法、Floyd-Warshall算法）、最小生成树问题（如Kruskal算法和Prim算法的部分优化）等。
(2)序列问题
序列比对、编辑距离、最长公共子序列、最长递增子序列等问题是动态规划的典型应用场景。
(3)资源分配问题
动态规划可用于解决资源分配问题，如背包问题、工厂生产调度问题等。
(4)游戏理论
在双人零和博弈、部分可观察马尔可夫决策过程（POMDP）等游戏中，可用动态规划来计算最优策略。
2．问题的主要适用特征
(1)重复子问题
动态规划通过存储已解决的子问题的结果（即记忆化），避免了重复计算。如果一个问题可以被分解为多个相似的子问题，那么动态规划通常是一个有效的解决方案。
(2)最优子结构
最优子结构指能通过解决子问题的最优解来找到原问题的最优解。也就是说如果解决了所有子问题，那么可以通过组合这些子问题的解来找到原问题的最优解。
(3)多阶段决策过程
多阶段决策指每个阶段都依赖于前一个阶段的决策。例如，在投资决策、资源分配或路径规划等问题中，每个决策点都依赖于之前的状态和决策。
3．适用条件
能用动态规划解决的问题必须要有无后效性（without Aftereffect）。无后效性也称子问题独立性（Independence of Subproblems）。
所谓的无后效性说白了就是不会“后反劲儿”，就像某人在路上被车闪了一下腰，该检查检查，该赔偿赔偿，赔偿完事就了了，不能说过个三年五载腰疼了再找人家算账。
也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，后续过程的演变不再受此前各种状态及决策的影响。
从子问题独立性角度看，是指每个子问题都是离散的，即不依赖于其他子问题，这样动态规划才管用。比如在伦敦的多个地方玩，每个地方都是独立的，这种情况可以用动态规划；但如果在伦敦玩完又要去巴黎玩，由于中间有一段伦敦到巴黎的路程，也需要时间，导致巴黎每个玩的地方游玩时间是相互依赖的（不是独立的，只有第一个去玩的地方要考虑伦敦到巴黎的时间），就不能用动态规划。
四、动态规划体验馆
纸上得来终觉浅，搞两个动态规划问题让列位体验一下看不懂的感觉。
1．子数组最大和
一个元素为整数（数值可正可负）的数组，求这个数组连续元素（被称为子数组）之和的最大值是多少？
例如：
数组{-9, 5, 2, -7, 3}，和最大的子数组为{ 5, 2}，最大值为7。
数组{-9, 5, 2, -7, 8}，和最大的子数组为{ 5, 2, -7, 8}，最大值为8。
之所以叫子数组，是因为它的孩子也得像数组一样一个挨一个，即选出来的元素必须是连续的。这个问题也被称为求“连续子序列的最大和”。
这个问题最直接的求解方法是用穷举法。设数组为A[]，有n个元素，代码如下：
int MaxSubString(int* A, int n){
int max = -1e9; //初始值为负无穷大
int sum;
for(int i = 0; i < n; i++){
sum = 0;
for(int j = i; j < n; j++){
sum += A[j];
if(sum > max) max = sum;
}
}
return max;
}这种方法需要两重循环，时间复杂度为O(n^2)，效率比较低。
这时动态规划就派上用场了，时间复杂度为O(n)。
思路是把数组A划分左右两部分：第一个元素A[0]和后面的其他部分After={A[1], A[2], …… , A[n-1]}。假设数组A中“和最大的子数组”为{A[i], …… ,A[j])，无非有以下几种情况：
①和最大的子数组只和A[0]有关。即和最大子的数组只有一个元素，就是A[0]，此时0 = i = j。比如A[]={9, -5, -2, -7}时，和最大的子数组就是{9}。
②和最大的子数组和A[0]、After均有关，即和最大的子数组是由A[0]开始的子数组，此时0 = i < j。比如A[]={9, 5, -2, -7}时，和最大的子数组就是{9, 5}。注意，这时候After中的第一个元素一定是和最大的子数组中的元素，否则和最大的子数组必然与After无关。
③和最大的子数组只和After有关，即数组A和最大的子数组与数组After的和最大的子数组相同，此时0 < i。比如A[]={-9, -5, 2, 7}时，和最大的子数组就是{2, 7}。
数组A可以看成第一个元素（A[0]）和后面的部分（After）组成，同理，数组After本身同样可以像这样分成两部分。于是，这就可以将一个大问题(N个元素数组)转化为一个较小的问题(N-1个元素的数组)。
假设已经知道数组After的子数组的最大和为All[1]（All[i]指下标为i到n-1的数组的子数组的最大和），并且已经知道After中包含A[1]的子数组的最大和为Start[1]（Start[i] 指下标为i到n-1的数组的包含第i个元素的子数组的最大和）。那么可以得出A的子数组的最大和All[0] = max{ A[0], A[0] + start[1], All[1] }。通过这样的分析，可以看出这个问题无后效性（A[0]对All[1]没有任何影响），可以用动态规划来解决。代码如下：
int MaxSubString(int* A, int n){
int Start = A[n - 1];
int All = A[n - 1];
for(int i = n - 2; i >= 0; i--){ //从后向前遍历，反之亦可。
Start = max( A[i], A[i] + Start);
All = max(Start, All);
}
return All;
}2．背包问题
背包问题属于动态规划中的明星产品，只要接触过动态规划，必然就会碰到背包问题。话说有n件物品和一个容量为v的背包。第i件物品的体积是c[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
比如有5个商品，他们的体积为 c[5] = {3,5,2,7,4}；价值为 v[5] = {2,4,1,6,5}; 背包的体积为10。
这是最基础的背包问题，每种物品仅有一件，可以选择放或不放。
思路和“子数组最大和”一样，也是分成两部分：第i件物品、前i-1件物品。设将前i件物品装入容量为j的背包的最大价值为f[i][j]（注意这里说的是前i件物品，不是第i件物品。也就是说，f[i][j]指考虑从第1件一直到第i件物品装背包的最大价值）
分为两种情况：
①第i件物品不装入背包。显然最大价值和第i件物品无关，只和前i-1件物品有关。即此时的最大价值为前i-1件物品装入容量为v的背包的最大价值，其值为f[i-1][v]。
②第i件物品装入背包。此时最大价值肯定包含第i件物品，所以背包的容量分为两部分：第i件物品的体积c[i]、剩下的体积v-c[i]。对应地，背包内装入物品的最大价值也分为两部分：第i件物品的价值v[i]、前i-1件物品装入容量为v-c[i]的最大价值，即此时的最大价值为v[i] + f[i-1][v-c[i]]。
因为只有这两种情况，最后取①、②的最大值，就是要求的大价值。
根据以上分析可以递归地定义问题的最优解 f[i][v] = max{ f[i-1][v], v[i] + f[i-1][v - c[i]]}，这个玩艺就叫状态转移方程。
代码如下：
#include<iostream>
#define max(a,b) ((a) > (b) ? a : b)
int c[5] = {3,5,2,7,4};
int v[5] = {2,4,1,6,5};
int f[6][10] = {0};
//f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + w[i]}
int main()
{
for(int i = 1; i < 6; i++)
for(int j = 1; j < 10 ;j++)
{
if(c[i] > j)//如果背包的容量，放不下c[i]，则不选c[i]
f[i][j] = f[i-1][j];
else
{
f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + v[i]);//转移方程式
}
}
std::cout<<f[5][9];
return 0;
}01背包问题是最基本的动态规划问题，可以说是背包界最易懂的。不知你懂了没？
不懂怎么办？多看几遍喽！
这玩艺本来就是比较难，老金自认为已经讲得相对通俗易懂了，实在看不懂只能见谅了！