机试准备第19天

今天重点学习动态规划问题。在使用递归解决问题时可能会产生性能问题，动态规划算法是为了解决递归产生的性能问题。递归会产生大量的重复问题，可以用空间换时间，用一种数据结构记录所有已经解决的问题。以数据结构为核心，从小问题回归得到大问题。首先设计一个数据结构，记录不同规模的答案，数据结构采用从小到大的方式去生成。

第一题是放苹果，通过一个二维dp数组记录信息。

#include <stdio.h>
#include <cstring>
using namespace std;
int main()
{
    int dp[13][13] = {0};
    //dp[m][n]就是m个苹果放入n个盘子
    int m, n;
    while(scanf("%d%d", &m, &n)!=EOF){
        memset(dp, 0, 13*13);
        for(int i = 0;i<=m;i++){
            dp[i][1] = 1;//只有一个盘子
        }
        for(int i = 1;i<=n;i++){
            dp[1][i] = 1;//只放一个苹果
            dp[0][i] = 1;//1个苹果都不放
        }
        for(int i = 2;i <=  m;i++){
            for(int j = 2; j <=n;j++){
                if(i >= j){//applenum > platenum
                    dp[i][j] = dp[i][j-1] + dp[i-j][j];
                }
                else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        printf("%d\n",  dp[m][n]);
    }

    return 0;
}

第二题是吃糖果。简单动归，可以吃一块或者两块。

#include <stdio.h>
using namespace std;
int main(){
    int dp[20]={0};
    dp[1] = 1;//一块巧克力只有一种方案
    dp[2] = 2;//两块巧克力有两种方案
    int N;
    scanf("%d", &N);
    for(int i = 3;i<=N;i++){
        dp[i] = dp[i - 1]+dp[i-2];//可以选择吃一块或者吃两块
    }
    printf("%d", dp[N]);
}

下面学习和线性数据结构相关的动态规划问题，两个序列求最长公共子序列，一个序列内的最大子序列和等等。两个线性表或一个线性表和他本身做对比，希望得到最值，这种需要动态规划。

第三题是最长公共子序列。dp[i][j]表示0～i-1 0～j-1的子序列的最长公共长度，若当前遍历元素相同，则dp[i][j]=dp[i-1][j-1]+1，若不同，则dp[i][j]=max(dp[i][j-1], dp[i-1][j])。

#include <stdio.h>
#include  <string.h>
#include <algorithm>
using namespace std;
int dp[1002][1002];
int main(){
    int n, m;
    char s1[1001];
    char s2[1001];
    scanf("%d%d", &n, &m);
    scanf("%s%s", s1, s2);
    //dp[i][j] s1的前i个元素 s2前j个元素的最大公共长度
    
    for(int j = 0; j<=m;j++){
        dp[0][j] = 0;//s1的一个元素也没处理
    }
    for(int i = 0; i<=n;i++){
        dp[i][0] = 0;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            //s1[0]~si[i-1] s2[0]~s2[j-1]
            if(s1[i-1] == s2[j - 1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    printf("%d\n", dp[n][m]);
    
    
}

第四题是最长公共字串。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
short dp[10001][10001];
int main(){
    char s1[10001];
    char s2[10001];
    scanf("%s%s", s1,s2);
    int n = strlen(s1);
    int m = strlen(s2);
    for(int j = 0; j <= m;j++){
        dp[0][j] = 0;
    }
    for(int i = 0;i<=n;i++){
        dp[i][0] = 0;
    }
    short curmax = 0;
    for(int i = 1; i <= n;i++){
        for(int j = 1;j<=m;j++){
            if(s1[i-1]>='a'&&s1[i-1]<='z'&&s1[i-1] == s2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
                curmax = max(dp[i][j], curmax);
            }
            else {//连不起来
                dp[i][j]=0;
                
            }
        }
    }
    printf("%d\n", curmax);
    return 0;
}

第五题是最大子序列和，dp数组代表从头到下标i元素的最大序列和。

#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
    int N;
    scanf("%d", &N);
    vector<long> vec1;
    for(int i = 0; i<N;i++){
        int val;
        scanf("%d", &val);
        vec1.push_back(val);
    }
    int size = vec1.size();
    vector<long> res;
    res.push_back(vec1[0]);
    long curmax = res[0];
    for(int i = 1; i< vec1.size();i++){
        long curnum = max(res[i-1]+vec1[i], vec1[i]);
        res.push_back(curnum);
        curmax = max(curmax, curnum);
    }
    printf("%ld", curmax);
}

第六题是最大子矩阵。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        if(n == 0) break;
        vector<int> start(10002);//记录当前元素为结尾的最大连续子序列的起始下标
        vector<int> vec(10002);//记录数组元素
        vector<int> dp(10002);//以i为下标元素对应的最大连续子序列和
        for(int i = 0; i<n;i++){
            scanf("%d", &vec[i]);
        }
        dp[0] = vec[0];
        start[0] = 0;
        int curmax = dp[0];
        for(int i = 1; i<n;i++){
            int val1 = dp[i-1]+vec[i];
            int val2 = vec[i];
            if(val1>=val2){
                dp[i] = val1;
                start[i] = start[i-1];
            }
            else {
                dp[i] = vec[i];
                start[i] = i;
            }
            curmax = max(curmax, dp[i]);
        }
        if(curmax<0) printf("0 %d %d\n",vec[0],vec[n-1]);
        else {
            for(int i = 0;i < n;i++){
                if(dp[i] == curmax){
                    printf("%d %d %d\n", curmax, vec[start[i]], vec[i]);
                    break;
                }
            }
        }
    }
}

第七题是最大上升序列和。

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        int dp[1000];//下标为i 的最大上升序列和
        vector<int> vec;
        for(int i=0;i<n;i++){
            int val;
            scanf("%d", &val);
            vec.push_back(val);
        }
        int maxsum = 0;
        for(int i = 0; i<n;i++){
            dp[i] =vec[i];
            for(int j = 0; j<i;j++){
                if(vec[i]>vec[j]){
                    dp[i] = max(dp[j] + vec[i], dp[i]);
                }
            }
            maxsum = max(dp[i], maxsum);
        }
        
        printf("%d\n", maxsum);
    }
}

下面学习01背包问题，首先明确dp数组的含义，dp[i][j]代表下标为0～i之间的物品，任取然后放进容量为j的背包里。不放物品i，dp[i][j] = dp[i-1][j]，放物品i，dp[i][j] = dp[i-1][j-weight[i]] + value[i]。dp[i][j]为两者的最大值。明天继续。