动态规划

动态规划分为三步：定义数组元素含义，找到初始值，写状态转移方程，做多基本就没啥问题了，当然都会做之后还涉及到一个优化问题。

1. 最大序列和

#include <iostream>
using namespace std;
const int maxn = 1000000;
//定义d[i]为从0到i最大序列和
int main(){
    int n;
    while (cin>>n){
        int dp[maxn],a[maxn];
        for(int i = 0;i < n;i++)
            cin>>a[i];
        dp[0] = a[0];
        int sum = a[0];
        for(int i = 1;i < n;i++){
            dp[i] = max(dp[i-1] + a[i],a[i]);
            if(sum < dp[i])
                sum = dp[i];
        }
        cout<<sum<<endl;
    }
    return 0;
}

最长上升子序列 判断在某个数前面是不是有比他小的数

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn = 1005;
int main(){
    int n;
    while (cin>>n){
        int dp[maxn],number[maxn];
        for(int i = 0;i < n;i++){
            cin>>number[i];
        }
        for(int i = 0;i < n;i++)
            dp[i] = number[i];
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < i;j++){
                if(number[j] < number[i])
                    dp[i] = max(dp[j] + number[i],dp[i]);
            }
            ans = max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

最大公共子序列 注意循环的起始和判断的条件 注意区分开最长公共子串（前一字母相同的情况一样，但是如果不同则归0，即dp[i][j] = 0）

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn = 105;
int main(){
    string a,b;
    while (cin>>a>>b) {
        int dp[maxn][maxn];
        int len_a = a.length();
        int len_b = b.length();
        memset(dp, 0, sizeof(dp));
        for(int i = 1;i <= len_a;i++){
            for(int j = 1;j <= len_b;j++){
                if(a[i-1] == b[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        cout<<dp[len_a][len_b]<<endl;
    }
    return 0;
}

2. 背包问题
   分为三种类似，01背包，完全背包、多重背包，掌握好状态转移方程即可。

#include <iostream>
#include <memory.h>
using namespace std;
//0 1背包 这里注意有一个优化的地方就是将状态转移方程降维 因为每一个状态都仅仅对前一行状态有关
int main(){
    int n,w;
    while (cin>>w>>n){
        int weight[n],dp[w];
        for(int i = 1;i <= n;i++)
            cin>>weight[i];
        memset(dp,0, sizeof(dp));
        for(int i = 1;i <= n;i++) {
            for (int j = w; j >=  weight[i]; j--) {
                    dp[j] = max(dp[j], dp[j - weight[i]] + weight[i]);
            }
        }
            if (dp[w] == w)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;

    }
    return 0;
}

#include <iostream>
#include <memory.h>
using namespace std;
//完全背包 注意好优化的时候要正序
int main(){
    int n,w;
    while (cin>>n>>w){
        int weight[n],value[n];
        int dp[w];
        memset(dp,0, sizeof(dp));
        for(int i = 1;i <= n;i++)
            cin>>weight[i]>>value[i];
        for(int i = 1;i <= n;i++){
            for(int j = weight[i];j <= w;j++){
                    dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
            }
        }
        cout<<dp[w]<<endl;
    }
    return 0;
}

如果是问有多少种方案的话，就是把方程从max改成+，然后取消+value[i]

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn = 10005;
int main(){
    int n;
    while (cin>>n){
        int weight[maxn];
        for(int i = 1;i <= n;i++)
            cin>>weight[i];
        int dp[maxn];
        memset(dp,0, sizeof(dp));
        dp[0] = 1;
        for(int i = 1;i <= n;i++){
            for(int j = 40;j >= weight[i];j--)
                dp[j] = dp[j] + dp[j - weight[i]];
        }
        cout<<dp[40]<<endl;
    }
    return 0;
}