状态转移方程
从之前某个阶段的某个或某些状态状态到下一个状态之间的关系式，就叫做状态转移方程。
最优子结构
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到的性质叫做最优子结构。
最优子结构的产生往往是对状态转换方程结果的挑选。
无后效性
如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段i-1中（或多个有限历史阶段）的状态通过状态转移方程得来，与其它状态没有关系，特别是与未发生的状态没有关系。
上述三项都在讲同一个问题：该问题拥有递推式。该递推式就是状态转移方程，该递推式的等号右边下标都不会大于等号左边。
重叠子问题
动态规划将问题分解为子问题（一般两个）。然后子问题又会分解出子子问题，这些子问题的解都被存储起来，相同子问题的解将被重复利用。
这些子问题解的的时候从多个备选结果中选择最优的那个（比如最小，最大，之类的）。
备忘录
应该是所有动态规划为提中必备的一项。
该项是子问题，也就是存储了每个状态。
- 钢条切割：使用一维容器存储了不同长度钢条的利润
- 矩阵链乘法：每个子问题都有一个开始位置和结束位置，所以需要使用二维容器来存储。
- 最长公共子序列：每个字问题：第一个序列的结束位置，第二个序列的结束位置，所以也使用二维容器来存储。
大白话
动态规划是一种寻找问题最优解的方法。
这种方法将一个问题从状态的角度进行定义，同时定义前一个状态到后一个状态的状态转移方程，并存储每一个状态的最优解。以便后续状态使用。
上面这句话的意思其实就是：
保持问题给出的条件不变，但是改变问题的问法：
- 在钢条切割问题中，不同长度钢条的售价不变，但是将问题改为当钢条1米的时候，怎样利润最大，2米的时候曾阳利润最大，3米，4米……一直到问题所问的米数。
- 矩阵链乘法中，各个矩阵大小不变，但问题改为其中连续两个矩阵相乘时计算歩数最小是多少，连续三个，连续四个，连续五个……一直到问题所问个数。
- 在最长公共子序列中，两个子序列不变，将问题改为是否存在长度为1,2,3,4,5…的子序列长度。
改变问题的问法，同时也改变了解题的思路。从之前的状态推后来的状态。
在自底而上的方式中（递推）
这种方式的实现符合上述。
在自上而下的方式中（递归）
这种方式的实现也仍然是求的最开始的状态然后推后来的状态。
钢条切割问题
一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。如一个Pi如下：
长度i 1 2 3 4 5 6 7 8 9 10
价格Pi 1 5 8 9 10 17 17 20 24 30
采用上述来分析：
钢条长度为：1 不切割，2 不切割， 3不切割 ，4 切割2+2，5 切割2+3……
同时应该存储每个状态（钢条长度）的最大值：
自底而上：
int cal(const std::vector<int> lp, int len)
{
lpLen = lp.size() - 1;
int num(0); //记录循环次数
std::vector<int> p(len+1); //建立备忘
for(int i=1; i <= len; i++) //i代表长度，从1开始建立备忘
{
tmp = 0;
if ( i <= lpLen ) //让i<lpLen的时候，备忘录还不可用
{
for(int j = 0 ; j <= i;j++)
{
num++;
tmp = tmp > lp[j] + lp[i-j] ? tmp : lp[j] + lp[i-j];
}
}else{ //长度>lpLen以后备忘录已经可用了。
for(int j = 1 ; j < i/2 +1;j++)
{
num++;
tmp = tmp > p[j] + p[i-j] ? tmp : p[j] + p[i-j];
}
}
p[i] = tmp; //当确定找到了最大值，才添加
}
std::cout<<"num : "<<num<<std::endl;
return p[len];
}
在一边存一边读取备忘录的时候，备忘录什么时候可用是一个坑：
- 刚开始，备忘录中全是0，根本不能用。
- 只有当基本的方式都全了以后才可用。
也就是lp中可能的切割方式。 - 当长度>能够卖出的最长长度时，不存在不切割这种情况，所以
j从1开始。
但是，当长度小于等于卖出的最长长度时，是可以不切割的。
同时，切割的长度只需要从开始到总长度的一半即可，因为切割是对称的。
另外，代码中的lpLen使用其实是错的：
代码中lpLen假设的是基本的切割方式组合。但是实际中可能并不是和lpLen相等。
代码中的lpLen应该换成基本切割方式。比如如果将本题中5对应的利润改为16,那么就会有11中基本切割方式。此时代码的结果是错的。
如果我们不能知道问题的输入（也就是给定的条件）那么一般不能使用该方法。
自上而下
//子上而下
int cut(const std::vector<int> &lp, std::vector<int> &p ,int len)
{
int tmp = 0;
if(p[len] > 0) return p[len]; //使用备忘录
if(len == 0) return 0; //0的时候出点
if(len <= 10)
{
for(int i = 0;i <= len; i++)
{
tmp = std::max(tmp, lp[len-i]+lp[i]);
}
}else{
for(int i = 1 ;i <= len/2 +1 ; i++)
{ //这里两个都必须是cut*****
tmp = std::max(tmp,cut(lp,p,i)+cut(lp,p,len-i) );
}
}
p[len]=tmp;
return p[len];
}
int calT(const std::vector<int> lp , int len)
{
std::vector<int> p(len+1);
return cut(lp,p,len);
}
其中标*****的：
必须使用cut的原因是：此时备忘录还没建好，不能使用备忘录。所以必须使用cut。
对比这两种方式
- 两种方式都需要先建立备忘录。
- 子上而下的递归，并不需要去假设总共可能的基本切割方式。
但是自底而上的递推需要提前计算出基本的切割方式。
钢条切割问题的最优子结构和状态转换方程：
//i表示未切割部分长度，j表示切割的长度
f[i]=f[i-j]+max(f[j])
子问题重叠：
比如，固定米数钢条的最大利润是一样的。
矩阵链乘法
在该问题中，状态和子问题为：从在给定的矩阵链中，取连续的1,2,3,4,5个矩阵相乘的歩数。
比如，矩阵为：1015 1530 305 515 15*20
上述五个矩阵相乘。
当取1个的时候相乘的计算歩数 为0 。
2个时，一共有4中情况
3个时，一共有3中情况
4个时，一共两种情况
5个时，就一种情况
在3个矩阵相乘时，每一种情况都会用到2个矩阵相的结果，并从中选取最少歩数的结果。
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <vector>
int mulM(const std::vector<int> vec)
{
int len = vec.size();
int tmp = 0;
int vecNum = len - 1; //实际矩阵个数
std::vector<std::vector<int>> memo(len); //备忘录
for(int i = 0 ;i < memo.size() ; i++)
{
memo[i].resize(len);
}
for(int len = 2 ;len <= vecNum ; len++) //状态：长度从2开始。
{ //长为2的矩阵链在原矩阵链中的开始位置
for(int start = 1 ; start <= vecNum - len + 1 ;start++ )
{
tmp=INT_MAX;
int end = start + len -1;
for(int k = start ; k <= end -1 ; k++) //括号的位置
{
int memo1=memo[start][k];
int memo2=memo[k+1][end];
tmp = std::min(tmp,vec[start-1] * vec[k] * vec[start+len-1] + memo1 + memo2);
memo[start][end] = tmp;
}
}
}
for(int i = 0 ;i <= memo.size()-1 ; i++)
{
std::cout<<std::endl;
for(int j = 0 ; j < memo[i].size(); j++)
{
std::cout<<memo[i][j]<<" ";
}
std::cout<<std::endl;
}
return memo[1][vecNum];
}
代码讲解
备忘录中存储的是memo[start][end]在原有矩阵链中从start到end位置的子矩阵链相乘的最短歩数。
最长公共子序列
该问题也有用最优子结构：在某个公共子序列的基础上推更长的最优子结构。
这个的状态转换公式貌似不好写吧？
状态和子问题就变为：当在两个序列长度从1开始慢慢增长，其公共子序列最大是多少？
那备忘录也就是要记录两个公共子序列的长度，所以需要一个二维容器。
备忘录中memo[i][j],当第一个序列长i，第二个序列长j情况下的最长公共子系列。
这里其实也并不需要一个二外的容器。遍历仍然可以获得。
这样我们可以得到两个序列的最大公共子序列的长度，但是无法获得其值，所以有需要一个容器来存储相等的部分。
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
std::string lcs(const std::string &l,const std::string &r)
{
int ll = l.size();
int rl = r.size();
std::vector<std::vector<int> > memo(ll+1,std::vector<int>(rl+1));
std::vector<std::vector<int> > memoRebuild(ll+1,std::vector<int>(rl+1));
for(int inL = 1; inL <= ll ;inL ++)
{
for(int inR = 1; inR <= rl ;inR ++)
{
if(l[inL-1] == r[inR-1])
{
memo[inL][inR] = memo[inL-1][inR-1]+1;
memoRebuild[inL][inR]=3;
}else if(memo[inL][inR-1] > memo[inL-1][inR]){
memo[inL][inR]=memo[inL][inR-1];
memoRebuild[inL][inR]=2;
}else{
memo[inL][inR]=memo[inL-1][inR];
memoRebuild[inL][inR]=1;
}
}
}
int reL = memoRebuild.size()-1;
int reR = memoRebuild[0].size()-1;
std::string re;
while(reL >= 0 && reR >= 0)
{
if(memoRebuild[reL][reR]==3)
{
re.push_back(l[reL-1]);
reL--; reR--;
}else if(memoRebuild[reL][reR] == 1)
{
reL--;
}else{
reR--;
}
}
std::cout<<"result ; "<<re<<std::endl;
return re;
}
从上面的代码中，不难发现，其实构造好备忘录才是本质
