[数据结构与算法]算法|动态规划

递推求解

n阶楼梯上楼问题|华中科大考研复试

描述
N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）
输入描述：
输入包括一个整数N,(1<=N<90)。
输出描述：
可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN=91;
long long dp[MAXN];

int main(){
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<MAXN;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%lld\n",dp[n]);
    }
    return 0;
}

吃糖果|北大考研复试

描述
名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。 妈妈告诉名名每天可以吃一块或者两块巧克力。 假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。 例如： 如果N=1，则名名第1天就吃掉它，共有1种方案； 如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案； 如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案； 如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。 现在给定N，请你写程序求出名名吃巧克力的方案数目。
输入描述：
输入只有1行，即整数N。
输出描述：
可能有多组测试数据，对于每组数据， 输出只有1行，即名名吃巧克力的方案数。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=21;
int dp[maxn];
int main(){
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<maxn;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",dp[n]);
    }
    return 0;
}

最大连续子序列和

最大序列和|清华考研复试

描述
给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,263-1）以内。
输入描述：
第一行为一个正整数N，第二行为N个整数，表示序列中的数。
输出描述：
输入可能包括多组数据，对于每一组输入数据， 仅输出一个数，表示最大序列和。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;

const int MAXN=1000000;

long long arr[MAXN];
long long dp[MAXN];

long long MaxSubsequence(int n){
    long long maximum=-INT_MAX;//不能直接设置成0的原因：有负数
    for(int i=0;i<n;i++){
        if(i==0) dp[i]=arr[i];
        else dp[i]=max(arr[i],dp[i-1]+arr[i]);
        maximum=max(maximum,dp[i]);
    }
    return maximum;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%lld",&arr[i]);
        }
        long long answer=MaxSubsequence(n);
        printf("%lld\n",answer);
    }
    return 0;
}

最大子矩阵和

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
const int maxn=100;

int matrix[maxn][maxn];//原始矩阵
int total[maxn][maxn];//辅助矩阵
int arr[maxn];//一维数组
int dp[maxn];

int MaxSubsequence(int n){
    int maximum=-INT_MAX;
    for(int i=0;i<n;i++){
        if(i==0) dp[i]=arr[i];
        else dp[i]=max(arr[i],dp[i-1]+arr[i]);
        maximum=max(maximum,dp[i]);
    }
    return maximum;
}

int MaxSubmatrix(int n){
    int maximal=-INT_MAX;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=0;k<n;k++) {//获得一维数组
                if (i == 0) arr[k] = total[j][k];
                else arr[k] = total[j][k] - total[i - 1][k];
            }
            int current=MaxSubsequence(n);
            maximal=max(maximal,current);
        }
    }
    return maximal;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++) {
            for (int j = 0; j < n; j++){
                scanf("%d",&matrix[i][j]);
            }
        }
        for(int i=0;i<n;i++){//初始化辅助函数
            for(int j=0;j<n;j++){
                if(i==0) total[i][j]=matrix[i][j];
                else total[i][j]=total[i-1][j]+matrix[i][j];
            }
        }
        int answer=MaxSubmatrix(n);
        printf("%d\n",answer);
    }
    return 0;
}

最大连续子序列|浙大考研复试

描述
给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。
输入描述：
测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K< 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。
输出描述：
对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。

#include<math.h>
using namespace std;
const int maxn=10000;
int arr[maxn];
int dp[maxn];
int K; 
void MaxSubsquence(int n){
   if(n==1){
       cout<<arr[0]<<" "<<arr[0]<<" "<<arr[0]<<endl;return ;
   }
   int sum=0,max1=arr[0],before=0,end=0;
   dp[0]=arr[0];
   if(arr[0]<0) sum++;
   for(int i=1;i<n;i++){
       dp[i]=max(arr[i],(dp[i-1]+arr[i]));
       if(arr[i]<0)sum++;
       if(max1<dp[i]){
           max1=dp[i];
           end=i; //如果有相同的最长子序列和，通过end记录下标靠前的。
       }
   } 
   if(sum==n){  //记录负数，全为负数的话输出0
       cout<<0<<" "<<arr[0]<<" "<<arr[n-1]<<endl;
   }else{
       int i=end;
       while(dp[i]>=0&&i>-1)i--; //从end往前找到第一个小于0的，然后再加一 就是序列的begin
       cout<<max1<<" "<<arr[++i]<<" "<<arr[end]<<endl;    
   }
}
int main(){
   while(cin>>K){
       if(K==0)break;
       for(int i=0;i<K;i++){
           cin>>arr[i];
       }
       MaxSubsquence(K);
   }
   return 0;
} 

最长递增子序列

拦截导弹|北京大学考研复试

描述
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
输入描述：
每组输入有两行， 第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25）， 第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
输出描述：
每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=25;

int height[MAXN];//导弹高度
int dp[MAXN];

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&height[i]);
        }
        int answer=0;
        for(int i=0;i<n;i++){
            dp[i]=1;//初始化为1
            for(int j=0;j<i;j++){
                if(height[i]<=height[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            answer=max(answer,dp[i]);//dp数组的最大值
        }
        printf("%d\n",answer);
    }
    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)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。
输入描述：
输入包含多组测试数据。 每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。
输出描述：
对于每组测试数据，输出其最大上升子序列和。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000;

int arr[maxn];
int dp[maxn];

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        int answer=0;
        for(int i=0;i<n;i++){
            dp[i]=arr[i];//初始化为arr[i]
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]){
                    dp[i]=max(dp[i],dp[j]+arr[i]);
                }
            }
            answer=max(answer,dp[i]);//dp数组的最大值
        }
        printf("%d\n",answer);
    }
    return 0;
}

合唱队形

描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK， 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述：
输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。 第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
输出描述：
可能包括多组测试数据，对于每组数据， 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

#include<bits/stdc++.h>
using namespace std;

const int maxn=300;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int dp1[maxn];//左边最大升序子序列的长度
        int dp2[maxn];//右边最长降序子序列的长度
        int A[maxn];
        for(int i=0;i<n;i++){
            scanf("%d",&A[i]);//输入
        }
        //从前往后寻找以i点为尾的最长递增子列
        for(int i=0;i<n;i++){
            dp1[i]=1;
            for(int j=0;j<i;j++){
                if(A[i]>A[j]){
                    dp1[i]=max(dp1[i],dp1[j]+1);
                }
            }
        }
        //从后往前寻找以i点为尾的最长递增子列
        for(int i=n-1;i>=0;i--){
            dp2[i]=1;
            for(int j=n-1;j>i;j--){
                if(A[j]<A[i]){
                    dp2[i]=max(dp2[i],dp2[j]+1);
                }
            }
        }
        int ans=1;
        //寻找点i两个子列的和的最大值
        for(int i=0;i<n;i++){
            if(dp1[i]+dp2[i]>ans){
                ans=dp1[i]+dp2[i];
            }
        }
        printf("%d\n",n-ans+1);//重复减了自身两次，故加1       
    }
    return 0;
}

最长公共子序列

描述
Find a longest common subsequence of two strings.
输入描述：
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
输出描述：
For each case, output k – the length of a longest common subsequence in one line.

#include<bits/stdc++.h>
using namespace std;

int main(){
    string a,b;
    while(cin>>a>>b) {
        int len1 = a.size();
        int len2 = b.size();
        int dp[len1 + 1][len2 + 1];
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;
                else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
        cout<<dp[len1][len2]<<endl;
    }
    return 0;
}