动态规划

——主要参考了中国大学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;
}