——主要参考了中国大学MOOC程序设计与算法（二）算法基础课程的内容
将一个问题分解为递归求解，并且将中间结果保存以避免重复计算的办法，可以称为“动态规划”。动态规划通常用来求最优解。能用动态规划解决的求最优解问题，必须满足最优解的每个局部解也都是最优的。
用动态规划解题，首先要把原问题分解为若干个子问题，这一点和前面的递归方法类似。区别在于，单纯的递归往往会导致子问题被重复计算，而用动态规划的方法，子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。再用动态规划解题时，往往将和子问题相关的各个变量一组取值称为一个“状态”。一个“状态”对应于一个或多个子问题。所谓某个状态下的值，就是这个状态所对应的子问题的解。定义出什么是状态，以及在该状态下的值后，就要找出不同的状态之间如何迁移——即如何从一个或多个值已知的状态，求出另一个状态的值。状态的迁移可以用递推公示表示，此递推公式也被称作状态转移方程。
能用动态规划求解的问题需要满足两个条件：1，问题具有最优子结构性质。2，无后效性。
01背包问题——动态规划例题
给定 N 种物品和一个容量为 M 的背包，物品 i 的重量是 w，其价值为 v。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
这个题目的代码很简单，关键在于思路，这是一个动态规划的题，需要先设定状态。记为前
种物品中取若干种，其体积不超过
的条件下获得的最大价值。可以得出如下的公式：
上面这个公式之后，代码就比较好写了，这个是一个递推的公式，可以使用滚动数组节约空间，代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int N,M;//N总物品和容积为M的背包
int goods[13000];//记录不超过下标i的体积的最大价值
struct Item{
int w;//体积
int v;//价值
};
Item items[3500];//记录每种物品的体积和价值
int main(){
cin>>N>>M;
for(int i=1;i<=N;i++){
int w,v;
cin>>w>>v;
items[i] = Item{w,v};
}
//取第一个物品
for(int i=0;i<=M;i++){
if(i>=items[1].w){
goods[i] = items[1].v;
}else{
goods[i] = 0;
}
}
//从第二件物品开始取
for(int i=2;i<=N;i++){
for(int j=M;j>=0;j--){
//避免出现负数，导致数组越界
if(items[i].w<=j){
goods[j] = max(goods[j],goods[j-items[i].w]+items[i].v);
}
}
}
cout<<goods[M]<<endl;
return 0;
}
最长上升子序列
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int n;
cin>>n;
int *arr = new int[n];
int *max = new int[n];
int *arr2 = new int[n];
for(int i=0;i<n;i++){
cin>>arr[i];
max[i] = 1;
arr2[i] = arr[i];
}
int ret = 1;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(arr[i] > arr[j]){
if(max[i] < max[j] + 1){
max[i] = max[j] + 1;
}else{
if(max[i] < max[j]){
max[i] = max[j];
arr2[i] = arr2[j];
}
}
}
}
if(max[i] > ret){
ret = max[i];
}
}
cout<<ret<<endl;
delete []arr;
delete []arr2;
delete []max;
return 0;
}
