机器学习

动态规划

动态规划（Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说，动态规划就是将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解过的子问题的解记录下来，这样当下次碰到相同的子问题时，就可以直接使用之前记录的结果，而不是重复计算。

关键:每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划(DP)。

核心：如何设计状态和状态转移方程

0-1背包问题

二维数组

#include<iostream>
using namespace std;
//二维数组形式
/*
5 8
3 4
5 5
1 2
2 1
2 3
*/
const int N=10000;
int dp[N][N],w[N],v[N];//w数组存储物品重量 v数组存储物品价值
int main()
{
	int n,m;//物品数量 背包容量
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j>=w[i])
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//核心递推式
			else dp[i][j]=dp[i-1][j];
		}
	}
	
	cout<<"max = "<<dp[n][m]<<endl;	
	
	return 0;
}

滚动数组一维优化

#include<iostream>
using namespace std;
//滚动一维数组
/*
5 8
3 4
5 5
1 2
2 1
2 3
*/
const int N=10000;
int dp[N],w[N],v[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)//逆序更新dp数组，因为dp[j]依赖于dp表左上方的值来进行更新
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<"max = "<<dp[m]<<endl;
	
	return 0;
}

完全背包问题

二维数组

#include<iostream>
#include<cmath>
using namespace std;
//二维数组
/* 4 10
   3 3
   2 1
   4 5
   7 9
*/
const int N = 10000;
int dp[N][N];
int w[N],v[N];//w数组存放重量，v数组存放价值
int main() {
	int n,m;
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++) {
		cin>>w[i]>>v[i];
	}
	for(int i = 1 ; i<=n ; i++)
		for(int j = 1; j<=m ; j++) {
			if(j>=w[i])
				dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i]);/*核心递推式 与0-1背包区别是dp[i][j-w[i]]+v[i]，而0-1背包是dp[i-1][j-w[i]]+v[i]*/
			else
				dp[i][j]=dp[i-1][j];
		}

	cout<<dp[n][m]<<endl;
	return 0;
}

一维滚动数组

#include<iostream>
#include<cmath>
using namespace std;
//一维滚动数组
/* 4 10
   3 3
   2 1
   4 5
   7 9
*/
const int N = 1010;
int dp[N];
int w[N],v[N];//质量 价值
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= m; j++)//注意了，这里的j是从小到大枚举，和01背包不一样,01背包必须逆序
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    cout << "maxn="<<dp[m] << endl;

    return 0;
}

最长连续子序列之和

#include<iostream>
#include<algorithm>
using namespace std;
#define maxn=200010
int arr[maxn],dp[maxn];//arr[i]存放序列 dp[i]存放以arr[i]结尾的连续序列之和
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	dp[0]=arr[0];//边界
	for(int i=1;i<n;i++)
	{
		dp[i]=max(arr[i],dp[i-1]+arr[i]);//状态转移方程
	}
	int k=0;
	for(int i=1;i<n;i++)
	{
		if(dp[i]>dp[k])//寻找最大值
		{
			k=i;
		}
	}
	cout<<dp[k]<<endl;
	
	
	
	return 0;
}
//输入
//6
//-2 11 -4 13 -5 -2
//输出 20

最长不下降子序列(LIS)

在一个数字序列中找到一个最长的子序列（可以不连续），使得这个序列是不下降的（非递减的).

#include<iostream>
#include<algorithm>
/*
输入：8
1 2 3 -9 3 9 0 11
输出：6
*/
using namespace std;
const int N=1000;
int A[N],dp[N];
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)cin>>A[i];
	int ans=-1;//记录最大值的dp[i]
	for(int i=1; i<=n; i++) {
		dp[i]=1;//边界初始条件
		for(int j=1; j<i; j++) {
			if(A[i]>=A[j]&&dp[j]+1>dp[i]) {//转移方程
				dp[i]=dp[j]+1;
			}
		}
		ans=max(dp[i],ans);
	}
	cout<<ans<<endl;
	return 0;
}

最长公共子序列（LCS）

给定两个字符串（或者数字序列）A和B,求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
char A[N],B[N];//A B字符串
int dp[N][N];
int main()
{
	int n;
	cin>>n;
	gets(A+1);//从下标1开始读入
	gets(B+1);
	int lenA=strlen(A+1);//由于读入时从下标1开始，因此读取长度也是从1开始
	int lenB=strlen(B+1);
	//边界初始化
	for(int i=0;i<=lenA;i++)
	{
		dp[i][0]=0;
	}
	for(int j=0;j<=lenB;j++)
	{
		dp[0][j]=0;
	}
	//状态转移方程
	for(int i=1;i<=lenA;i++)
	{
		for(int j=1;j<=lenB;j++)
		{
			if(A[i]==B[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;//如果相同，则从dp表左上角+1赋值
			}
			else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);//不相同 则取左边或者上面较大的赋值
		}
	}
	cout<<dp[lenA][lenB]<<endl;
	return 0;
}

最长回文子串

给出一个字符串S，求S的最长回文子串的长度

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
using namespace std;
const int maxn=10010;
char S[maxn];
int dp[maxn][maxn];

int main()
{
	gets(S);//从下标0开始读入字符串
	int len=strlen(S),ans=-1;
	memset(dp,0,sizeof(dp));//初始化
	//边界
	for(int i=0;i<len;i++)
	{
		dp[i][i]=1;
		if(i<len-1)
		{
			if(S[i]==S[i+1])
			{
				dp[i][i+1]=1;
				ans=2;//初始化时注意当前最长回文子串长度
			}
		}
	}
	//状态转移方程
	for(int L=3;L<=len;L++)//枚举子串的长度
	{
		for(int i=0;i+L-1<len;i++)//枚举子串的起始端点
		{
			int j=i+L-1;//子串的右端点
			if(S[i]==S[j]&&dp[i+1][j-1]==1)
			{
				dp[i][j]=1;
				ans=L;//更新回文子串长度
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

DAG（有向无环图）最长路

求整个DAG的最长路径（即不固定起点和终点）

给定一个有向无环图，怎么求解整个图所有路径中权值之和最大的那条。

令dp[i]表示从i号顶点出发能获得的最长路径长度，这样所有dp[i]中的最大值就是整个DAG的最长路径。

int DP(int i){
    if(dp[i] > 0) return dp[i];//dp[i]已计算完毕
    for (int j = 0; j < n; ++j)//遍历i的所有出边
    {
        if(G[i][j] != INF){
            dp[i] = max(dp[i], DP(j)+G[i][j]);
        }
    }
    return dp[i];//返回计算完毕的dp[i]
}

从出度为0的顶点出发的最长路径长度为0，因此边界为这些顶点的dp值为0。
但具体实现，可以对整个数组dp初始化为0，这样dp函数当前访问的顶点i的出度为0时，就会返回dp[i]= 0(以此为dp的边界)，而出度不为0的顶点则会递归求解，递归过程中遇到已经计算过的顶点，则会直接返回对应的dp值。

求解最长路径

可以开一个int型数组choice来记录最长路径上顶点的后继顶点。【如果存在多条最长路径，把choice数组改为vector数组】

int DP(int i){
    if(dp[i] > 0) return dp[i];//dp[i]已计算完毕
    for (int j = 0; j < n; ++j)//遍历i的所有出边
    {
        if(G[i][j] != INF){
            int temp = DP(j) + G[i][j];//单独计算，防止if调用DP函数两次
            if(temp > dp[i]){
                dp[i] = temp;
                choice[i] = j;
            }
        }
    }
    return dp[i];//返回计算完毕的dp[i]
}

//调用前，要先求出最大的dp[i],然后将i作为路径起点传人
void printPath(int i){
    printf("%d\n", i);
    while(choice[i] != -1){//choice初始化为-1
        i = choice[i];
        printf("->%d\n", i);
    }
}

• 记录每次决策所选择的策略，然后在dp数组计算完毕之后，根据具体情况进行递归或迭代来获取方案。

实际例题

问题 A: 矩形嵌套

题目描述
有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。
输入
第一行是一个正正数N(0<N<10)，表示测试数据组数，
每组测试数据的第一行是一个正正数n，表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行，每行有两个数a,b(0<a,b<100)，表示矩形的长和宽
输出
每组测试数据都输出一个数，表示最多符合条件的矩形数目，每组输出占一行

样例输入 
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
样例输出 
5

代码如下：

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1010;
const int INF = -1000000000;
int dp[MAXN];
int G[MAXN][MAXN];
int edge[MAXN][MAXN];
int n;

//求最长路径长度
int Dp(int i){
    if(dp[i] > 0) return dp[i];

    for (int j = 0; j < n; ++j)
    {
        if(G[i][j] != 0){
            int temp = Dp(j) + G[i][j];
            if(temp > dp[i]){
                dp[i] = temp;
            }
        }
    }

    return dp[i];
}

int main(int argc, char const *argv[])
{
    int N;
    scanf("%d", &N);
    while(N--){
        memset(G, 0, sizeof(G));//初始化
        fill(dp, dp + MAXN, 0);

        scanf("%d", &n);

        int a = 0, b = 0, maxIndex;
        for (int i = 0; i < n; ++i)
        {
            scanf("%d%d", &edge[i][0], &edge[i][1]);

            if(edge[i][0] < edge[i][1]){//长的边靠前
                swap(edge[i][0], edge[i][1]);
            }

            if(edge[i][0] > a && edge[i][1] > b){//求最大的矩形，即源点
                a = edge[i][0];
                b = edge[i][1];
                maxIndex = i;
            }

            for (int j = 0; j < i; ++j)//构建有向图
            {
                if(edge[i][0] > edge[j][0] && edge[i][1] > edge[j][1]){//矩形i能嵌套矩形j
                    G[i][j] = 1;
                }else if(edge[i][0] < edge[j][0] && edge[i][1] < edge[j][1]){//矩形j能被矩形i嵌套
                    G[j][i] = 1;
                }
            }
        }
        int ans = Dp(maxIndex);
        printf("%d\n", ans + 1);//顶点数为最长路径长度（边数）+1
    }
    return 0;
}