动态规划详解（1）
目录
简介(入门篇)
什么是动态规划，我们要如何描述它?
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。
现在让我们通过一个例子来了解一下DP的基本原理。
首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。
“状态”代表什么及如何找到它?
“状态"用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚，跳过直接上例子。
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)
首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？为什么要这么问呢？两个原因：1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。 2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。
好了，让我们从最小的i开始吧。
当i=0，即我们需要多少个硬币来凑够0元。由于1，3，5都大于0，即没有比0小的币值，因此凑够0元我们最少需要0个硬币。 (这个分析很傻是不是？别着急，这个思路有利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。”会比较方便，如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。那么，我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。
当i=2时，仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币！耐心点，让我们看看i=3时的情况。
当i=3时，我们能用的硬币就有两种了：1元的和3元的( 5元的仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了一个1元的硬币，我的目标就变为了：凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。这个方案说的是，我拿3个1元的硬币；第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是，我拿1个3元的硬币。好了，这两种方案哪种更优呢？记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。
OK，码了这么多字讲具体的东西，让我们来点抽象的。从以上的文字中，我们要抽出动态规划里非常重要的两个概念：状态和状态转移方程。
上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的"状态"，这个状态是怎么找出来的呢？我在另一篇文章 动态规划之背包问题(一)中写过：根据子问题定义状态。你找到子问题，状态也就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。没错，它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下：
d(i)=min{ d(i-vj)+1 }
其中i-vj >=0，vj表示第j个硬币的面值;有了状态和状态转移方程，这个问题基本上也就解决了。
初级篇
购买或销售股票的最佳时机
原题目如下：
翻译如下：
假设有一个数组，其对i个元素是一支给定的股票在某一天i的价格。
如果最多只允许你完成一次交易（例如，购买或销售一次该股票的份额），设计一个算法，来找到最大的赢利点。
求解：由于有两个变量，我们先假定一个变量，即在第N天卖出，那么其最佳买点就是前N天的最小值。因此问题转化为：遍历求解每一天出售可获取的最大利润。
难点在于求第i天前（包含第i天）的最低股票价格。
定义：min[i]表示第i天前最低股票价格，i>=1（i从0开始）
初始化：min[0]=prices[0]，便于边界处理递推表达式：min[i]=MIN{min[i-1],prices[i]}，i>=1（i从0开始）
C++实现如下：
// main
int main()
{
vector<int> x;//intput
//用来记录最小值，及相应的index
vector<pair<size_t,int>> memo;
// 记录买点 和 卖点
size_t min_index,max_index;
int max_profit(0),temp;
for(size_t i;i!=memo.size();++i)
{
temp=x[i]-minV(x,i);
if(temp>max_profit){
max_index=i;
min_index=memo[i].first;
max_profit=temp;
}
}
}
// the min value of stock prices before nth day
int minV(vector<int>& x, int n)
{
if(memo.size()>=n)
return memo[n-1].second;
else
{
if(n==1)
return x[0];
else
return (minV(x,n-1) < x[n-1])?minV(x,n-1) :x[n-1];
}
}
最长非降子序列
上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题，如何找到状态之间的转移方式(即找到状态转移方程)。为此我们要引入一个新词叫递推关系来将状态联系起来(说的还是状态转移方程)
OK，上例子，看看它是如何工作的。
一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS：longest increasing subsequence)
正如上面我们讲的，面对这样一个问题，我们首先要定义一个“状态”来代表它的子问题，并且找到它的解。注意，大部分情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态。
让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度，其中i<N，那么上面的问题变成了原问题的一个子问题(问题规模变小了，你可以让i=1,2,3等来分析) 然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。OK，对照“入门”中的简单题，你应该可以估计到这个d(i)就是我们要找的状态。如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。状态找到了，下一步找出状态转移方程。
为了方便理解我们是如何找到状态转移方程的，我先把下面的例子提到前面来讲。如果我们要求的这N个数的序列是：
5，3，4，8，6，7
根据上面找到的状态，我们可以得到：（下文的最长非降子序列都用LIS表示）
- 前1个数的LIS长度d(1)=1(序列：5)
- 前2个数的LIS长度d(2)=1(序列：3；3前面没有比3小的)
- 前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3，所以d(3)=d(2)+1)
- 前4个数的LIS长度d(4)=3(序列：3，4，8；8前面比它小的有3个数，所以 d(4)=max{d(1),d(2),d(3)}+1=3)
OK，分析到这，我觉得状态转移方程已经很明显了，如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：
d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
用大白话解释就是，想要求d(i)，就把i前面的各个子序列中，最后一个数不大于A[i]的序列长度加1，然后取出最大的长度即为d(i)。当然了，有可能i前面的各个子序列中最后一个数都大于A[i]，那么d(i)=1，即它自身成为一个长度为1的子序列。
分析完了，上图：(第二列表示前i个数中LIS的长度，第三列表示，LIS中到达当前这个数的上一个数的下标，根据这个可以求出LIS序列)
Talk is cheap, show you the code:
#include <iostream>
using namespace std;
int lis(int A[], int n){
int *d = new int[n];
int len = 1;
for(int i=0; i<n; ++i){
d[i] = 1;
for(int j=0; j<i; ++j)
if(A[j]<=A[i] && d[j]+1>d[i])
d[i] = d[j] + 1;
if(d[i]>len) len = d[i];
}
delete[] d;
return len;
}
int main(){
int A[] = {
5, 3, 4, 8, 6, 7
};
cout<<lis(A, 6)<<endl;
return 0;
}该算法的时间复杂度是O(n2 )，并不是最优的解法。还有一种很巧妙的算法可以将时间复杂度降到O(nlogn)，网上已经有各种文章介绍它，这里就不再赘述。
电梯调度问题
问题描述：
所有的员工均在1楼进电梯的时候，选择所要到达的楼层。
然后计算出停靠的楼层i，当到达楼层i的时候，电梯停止。
所有人走出电梯，步行到所在的楼层中。
求所有人爬的楼层数目和的最小值。
问题解决方法
-
使用简单的方法，直接将楼层从1到n开始遍历
sum(person[i] * |i - j| ) 此表达式为一个双重循环，i与j均为1-n的循环。
j下标表示电梯停靠的楼层。
person数组表示，对应i层的下电梯的人数。此算法复杂度为o(n^2)
对应的j是上述和为最小的一层即为所求。 上面的算法复杂度为o(n) -
使用动态规划的思想，使其复杂度达到o(n)
考虑假如电梯停靠在某一楼层i处，假设在i处下楼的客人为N2(i),在i以上楼层的客人数目为N3(i) ，在i以下楼层的客人数目为N1(i)。 且将电梯在i层停止时，全部人员的路程之和记为T(i)。
考虑在i+1层的结果，若电梯在i+1层停止的话，原来i层之上的客户都会少爬一层，
则结果减少N3 ，而i层之下的人员则都会多爬一层即增加了N1 ，第i层的人员都会多爬一层，即为增加了N2 。
则T(i+1)= T(i) + N1(i) + N2(i) - N3(i)
可以证明：若在第i层时出现N1 + N2 < N3，则算法可以直接退出，第i层即为所求。
即需要证明：N1(i+1)+N2(i+1)<N3(i+1) if N1(i)+N2(i)<N3(i)
N1(i+1)=N1(i)+N2(i);
N2(i+1)=Person(i+1);
N3(i+1)=N3(i)-Person(i+1);
所以有：
N1(i+1)+N2(i+1)-N3(i+1)=N1(i)+N2(i)-N3(i)-2Person(i)<0
得证
给出一个java实现如下：
public class DianTi
{
static final int N = 10 ;
static int person[] = {0, 2, 5 , 7 , 3 , 5 , 2 , 6, 2 , 6 , 3};
public static void main(String[] args)
{
System.out.print(compute(person));
}
public static int compute(int[] person)
{
//先计算出在第一层停止的时候 所需要的花费
int T = 0;
int N1 = 0 ; //在第一层以下下的人数
int N2 = person[1] ; //在第一层处下的人数
int N3 = 0 ; //在第一层之上下电梯的人数
int floor = 1 ;
//先计算出第1层停止需要爬取的楼层数目
for(int i = 2 ; i <= N ;i++)
{
T += person[i] * (i - 1) ;
N3 += person[i] ;
}
for(int i = 2 ; i <= N ;i++)
{
if(N1 + N2 <= N3) //说明第i+1层的结果会大于第i层
{
T += N1 + N2 - N3 ;
N1 += N2 ;
N2 = person[i] ;
N3 -= person[i] ;
floor = i ;
}
else //否则第i层的结果已经最小，故不需要计算第i+1层
break ;
}
return floor ;
}
}
中高级篇，且听下回分解。