【Algorithm】动态规划

矩阵连乘

代码其实……有点麻烦

详细解读

https://blog.csdn.net/qq_19782019/article/details/94356886

代码

// http://www.nbuoj.com/v8.83/Contests/Problem.php?cid=6743&nid=1  
#include <iostream>  
#include <algorithm>  
using namespace std;  
   
//输入矩阵的行列
int arr[2333];   
//m用来记录计算量
int m[2333][2333]={0};  
//s用来保存括号位置
int s[2333][2333]={0};   
//n是矩阵个数
int n;   
   
int main()  
{  
    cin >> n;  
    for (int i=0;i<=n;i++)  
        cin >>arr[i];  
    //r记录规模，从规模为2开始计算，如AB；r=3时，ABC，r=4，ABCD
       //ABCD都指一个矩阵
    for (int r=2;r<=n;r++){  
           //n-r+1 表示从某个矩阵最多后面要连接多少个其它矩阵
           //如A后面最多连接3个，B后面最多连接2个，C后面最多连接1个
        for (int i=1;i<=n-r+1;i++){ 
               //j的意思是，从i后面开始
            int j=i+r-1;  
            //对m[i][j]初始值进行设置
               //假设现在要连接D，让它假设为，直接连接到ABC后面，形成ABCD，先不管ABC是怎么连接的
               //ABC可能为A(BC)或(AB)C
            m[i][j]=m[i+1][j]+arr[i-1]*arr[i]*arr[j];  
            //s[i][j]是用来保存“括号”位置的，这里没用上
            s[i][j]=i;
               //k是在i~j之间，表示“括号”插入的位置
            for(int k=i+1;k<j;k++){
                   // temp记录，如果将“括号”插入在不同位置，再连乘后的计算量
                   // m[i][k]是A[i:k]的计算量，A泛指某个矩阵
                   // m[k+1][j]是A[k+1,j]的计算量
                   // arr[i-1]*arr[k]*arr[j]是  A[i:k]乘以A[k+1,j]  的计算量
                int temp=m[i][k]+m[k+i][j]+arr[i-1]*arr[k]*arr[j];  
                   
                   // 如果用这个算法得出的计算量temp，比“直接连接”的方法的计算量(刚刚初始的m[i][j])要少，则更新
                   // 如果括号插入在不同位置，计算量更少，也会更新
                if(m[i][j]>temp)  
                {  
                    m[i][j]=temp;  
                    s[i][j]=k;//记录括号的位置，这里没用上
                }  
            }  
        }  
    }  
    cout << m[1][n]<<endl;  
    return 0;  
}

举例

A=50*10,B=10*40,C=40*30,D=30*50

	A	B	C	D
A	0	AB 501040	A(BC) 27000	A(B(CD)) 10500
B		0	BC 104030 12000	B(CD) 8000
C			0	CD 40305 6000
D				0

从表格的左上开始，先AB,BC,CD,再[ABC],[BCD],再[ABCD]，中括号[]只是表示矩阵连乘的规模，不是顺序

m[A][B]=m[B][B]+50*10*40 形成AB
m[B][C]=m[C][C]+10*40*30 形成BC
m[A][C]=min{ m[A][A] 0 +m[B][C] 12000 +50*10*30 15000 共27000 相当于：A(BC),m[A][B] 20000 +m[C][C] 0 +50*40*30 60000 共80000 相当于：(A)BC}
m[A][C] 选择两个中小的，形成A(BC)

……

m[A][D]=min{ m[A][A] 0 +m[B][D] 8000 +50*10*50 25000 共33000 相当于：A[B~D] ,m[A][B] 20000 +m[C][D] 6000 +50*40*50 100000 共126000 相当于：[AB][CD] ,m[A][C] 27000 +m[D][D] 0 +50*30*50 75000 共102000 相当于： [A~C]D }

上面的[B~D]其实也会选择最小值，变成B(CD)
上面的[A~C]选择最小值，变成A(BC)
所以对m[A][D]最小的是A[B~D]也就是A(B(CD))

三角路径最大

题目

解析

我们不妨将金字塔倒过来

[     
  [4,1,8,3],
   [6,5,7],
    [3,4],
     [2]
]

我们只要再相邻的元素中选出最大的值，然后往对应的下一层加即可。

例如[4,1,8,3]，4和1比，所以我们将4加到下一层的6。接着，考虑1和8，我们将8加到下一层的5，接着考虑8和3，我们将8加到7，以此类推下去。

基于这个思想我们可以写出这样的代码

#include<iostream>  
#include<algorithm>  
using namespace std;  
int n;  
int *the_max;  
int arr[1005][1005]={0};  
int main()  
{  
    cin>>n;  
    for(int i=1;i<=n;i++){  
        for(int j=1;j<=i;j++){  
            cin>>arr[i][j];  
        }  
    }  
    the_max=arr[n];  
    //从倒数第一行倒序查找  
    for(int i=n;i>=2;i--){  
        //从第一列查找  
        for(int j=1;j<=i-1;j++){  
            //n-1行的值A加上A下方的两个值中最大者  
            arr[i-1][j]+=max(arr[i][j],arr[i][j+1]);  
        }  
    }  
       // res
    cout<<arr[1][1]<<endl;  
       for(int i=1;i<=n;i++){  
        for(int j=1;j<=i;j++){  
            cout<<arr[i][j]<<" ";  
        }  
           cout<<endl;
    } 
}

01背包

题目

野地里有许多不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。要求在规定的时间t里，采到的草药的总价值最大。

这里的总时间，就是背包总容量
每个草药需要的时间，就是每个物品需要的容量

代码

int time,herb,tcost[200],hvalue[200];
int f[2000];
int i,j;
int main() {
    //总时间，总草药数目
    scanf("%d %d",&time,&herb);
    //每个草药需要的时间和价值
    for(i=0;i<herb;i++)
    	scanf("%d %d",&tcost[i],&hvalue[i]);
    for(i=0;i<herb;i++)
        //肯定从最大背包容量开始装
    	for( j=time;j>=tcost[i];j--)
            //不采，和采 中选择其中价值最大的
            //f[j]表示，在容量最大为"j"的情况下，能装的最大价值
    		f[j]=max(f[j],f[j-tcost[i]]+hvalue[i]); 
    printf("%d\n",f[time]);
    return 0;
}

最长的非连续子序列

题目

在一个数字序列中，找到一个最长的非连续子序列，使得这个子序列是不下降（非递减）。现有序列A={1,2,3,-1,-2,7,9},则A的最长不下降子序列是{1,2,3,7,9}。

如果有多个最长序列，只需选数字顺位靠后的序列从大到小输出。

输入

31 96 27 -35 46 -96 0

输出

0 -96

代码

#include <iostream>  
   #define themax(a,b) a>b?a:b
using namespace std;  
  
int main() {  
    int n,res_index;  
    int arr[105]={0};  
    int dp[105]={0};  
    //记录结果路径的数组  
    int res_path[1005]={0};  
    cin>>n;  
    for(int i=0; i<n; i++) {  
        cin>>arr[i];  
        res_path[i]=0;  
           //dp初始设置为1，表示自身至少可以算一个
           dp[i]=1; 
    }  
    int res=-1;  
    for(int i=1; i<n; i++) {  
           //j可以从0开始，但递减开始的话，需要修改dp[i]的次数会更少些
        for(int j=i-1; j>=0; j--) {  
            //如果前一个数arr[j]不大于arr[i]而且，0到第j个数的连续不下降个数再加1(加1表示算上i后)  大于  0到第i个数的连续不下降个数  
            //则可以将第j个数的下一个连续数是i  
            if(arr[i]>=arr[j]){  
             	//第i个元素记录的值前一个元素的下标j
               //注意，要先判断是否来自于j，否则就会res_path[i]=i这种自己引入到自己……无意义
                       if(dp[j]+1>dp[i]){
                           res_path[i]=j;  
                       }
                    //dp[i]记录0到第i个数的连续不下降个数  
                    dp[i]=themax(dp[j]+1,dp[i]);                        
            }  
               /*
               上面的写法，不如直接把判断条件拿上来
               if(arr[i]>=arr[j]&&dp[j]+1>dp[i]){  
                       res_path[i]=j;
                    dp[i]=dp[j]+1;                 
            }  
               */
        }  
        res=max(res,dp[i]);  
    }  
    //找到结果序列的首元素下标  
    for(int i=n-1; i>=0; i--) {  
        if(res==dp[i]) {  
            res_index=i;  
            break;  
        }  
    }  
    cout<<res<<endl;  
    //输出路径  
    for(int i=n-1; i>=n-res+1; i--) {  
        cout<<arr[res_index]<<" ";  
        res_index=res_path[res_index];  
    }  
    cout<<arr[res_index]<<endl;  
}

最长公共子序列

题目与证明

https://blog.csdn.net/weixin_40522938/article/details/111223435

当Xm=Yn时，有
- Zk=Xm=Yn，Xm和Yn的LCS等于X(m-1)和Y(n-1)的LCS，状态1
当Xm!=Yn时，有
- Zk!=Xm，Xm和Yn的LCS等于Xm-1和Yn的LCS，状态2
- Zk!=Yn，Xm和Yn的LCS等于Xm和Yn-1的LCS，状态3
- 以上两种情况包含了Xm!=Yn时所有可能的情况，因为所求的LCS必然为以上两种情况中的一种，又因为求的是最长，所以所求LCS = Max(LCS2，LCS3)；

所以LCS的转移方程为

c[i][j]={0,i> 0 ; j=0c[i−1][j−1]+1,i,j>0; Xi=Yjmax{c[i][j−1],c[i−1][j]},i,j>0; Xi!=Yjc[i][j] = \begin{cases} 0, & \text{i> }0\text{ ; j=0} \\ c[i-1][j-1]+1, & \text{i,j>0; } \text{ Xi=Yj} \\ max\{c[i][j-1],c[i-1][j] \}, & \text{i,j>0;} \text{ Xi!=Yj} \end{cases} c[i][j]=⎩⎪⎪⎨⎪⎪⎧0,c[i−1][j−1]+1,max{c[i][j−1],c[i−1][j]},i> 0 ; j=0i,j>0; Xi=Yji,j>0; Xi!=Yj

//如果只求最大值
if(x[i]=y[j]){
	c[i][j]=c[i-1][j-1]+1;
}
else{
    c[i][j]=max(c[i-1][j],c[i][j-1]);
}


//如果需要记录是哪个字符，新增一个b数组
if(x[i]=y[j]){
	c[i][j]=c[i-1][j-1]+1;
    //b数组用来记录是哪些符号，如果只要求最大值，没必要有b数组
    //状态1
	b[i][j]=1;
}
else if(c[i-1][j]>c[i][j-1]){
    //表示X(m-1)Y比XY(n-1)更大
    c[i][j]=c[i-1][j];
    //状态2
	b[i][j]=2;
}
else{
    //表示XY(n-1)比X(m-1)Y更大
    c[i][j]=c[i][j-1];
    //状态3
	b[i][j]=3;
}

/*
	b数组是上面的函数用来记录状态的
*/
void LCS(int i,int j,char *x,int **b){
    if(i==0||j==0)
        return 0;
    if(b[i][j]==1){
        //状态1
        LCS(i-1,j-1,x,b);
        //输出x,y相同的字符
        cout<<x[i];
    }
    else if(b[i][j]==2){
        //状态2，说明与X(m-1)Y一样
        LCS(i-1,j,x,b);
    }else{
        //状态3，说明与XY(n-1)一样
        LCS(i,j-1,x,b);
    }
}

最大子段和

子段要求连续

输入 -2,11,-4,13,-5,-2 输出20；

int MaxSum(int n,int *arr){
    //theMax是当前累积最大值
    //b是前几个数
	int theMax=0,b=0;
    for(int i=0;i<n;i++){
        //一旦前面几个数的和小于0，则抛弃前面的
        //如 11 2 4 -100 20.读头到20时，b已经小于0了，b直接抛弃原来值并令b=20
		if(b<=0)
            b=arr[i];
        else{
            b+=arr[i];
        }
        if(b>theMax)
            theMax=b;
    }
}