• 算法笔记-第十章-动态规划2

    算法笔记-第十章-动态规划2

    最大连续子序列和

    对于最大连续数组求和的问题，设置一个dp数组，然后进行分开讨论边界的问题：
    1.最大和就是A[i]本身
    2.最大和是dp[i-1]+A[i]，即A[P]+…A[i-1]+A[i]=dp[i-1]+A[i]

    由于这两种情况，于是得到了状态转移方程：dp[i]=max(A[i],dp[i-1]+A[i])

    在这里插入图片描述

    //最大连续子序列之和
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 10000;
const int INF = 0x3fffffff;
int a[MAXN];//a[i]存放序列，dp[i]存放以A[i]结尾的连续序列的最大和
int dp[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    dp[0] = a[0];  

    //状态转移方程  
    for (int i = 1; i < n; i++) {  
        dp[i] = max(a[i], dp[i - 1] + a[i]);  
    }
    //dp[i]存放以a[i]结尾的连续序列的最大和，需要便利i得到最大的才是结果  
    int maxResult = -INF;  

    for (int i = 0; i < n; i++) {  
        maxResult = max(maxResult, dp[i]);  
    }
    printf("%d", maxResult);  
    return 0;  
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    最大连续子序列和的最优方案

    在这里插入图片描述
    在这里插入图片描述

    //最大连续子序列和的最优方案
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 10000;
int a[MAXN];
int dp[MAXN], start[MAXN];//开始和结束的下标数组

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    dp[0] = a[0];

    start[0] = 0;

    for (int i = 1; i < n; i++) {
        if (dp[i - 1] >= 0) {
            dp[i] = dp[i - 1] + a[i];

            start[i] = start[i - 1];
        }
        else {  
            dp[i] = a[i];  

            start[i] = i;  
        }
    }
    int k = 0;  
    for (int i = 1; i < n; i++) {  
        if (dp[i] > dp[k]) {  
            k = i;  
        }
    }
    printf("%d %d %d", dp[k], start[k] + 1, k + 1);  
    return 0;  
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    最长上升子序列

    在这里插入图片描述

    在这里插入图片描述

    问题分析：
    最原始的方法就是暴力解法，枚举每一种情况 ，即对于每个元素有取和不取两种选择，然后进行判断序列是否为不下降序列。

    如果没有则更新最大长度，知道枚举完所有的情况并且得到最大长度。

    • 1.方法就是：令dp[i]表示以A[i]结尾的最长不下降序列长度(和最大连续子序列和问题一样，以A[i]结尾是强制性的要求，对于A[i]就有着两种可能性

    • 2.如果存在A[i]之前的元素A[j],(jdp[i],(即把A[i]跟在以A[j]结尾的LIS后面能比当前以A[i]结尾的LIS长度更长), 那么就把A[i]，跟在以A[j]，结尾的LIS后面，形成一条更长的不下降序列。(dp[i]=dp[j]+1)

    • 3.如果A[i]之前的元素都比A[j]大，那么A[i]就只好自己形成一条LIS，但是长度为1，即这个子序列里面只有一个A[i]。

    • 那么A[i]结尾的LIS长度就是两个情况的最大长度。

    #include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100;
int a[MAXN];
int dp[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int maxLen = 0;//记录最大的dp[i] 

    for (int i = 0; i < n; i++) {//按照顺序计算出dp[i]的值 
        dp[i] = 1;//边界初始化条件，(即先假设每一个元素自成一个子序列） 
        for (int j = 0; j < i; j++) { 

            if (a[j] <= a[i] && dp[j] + 1 > dp[i]) {  
                dp[i] = dp[j] + 1;//状态转移方程，用以更新dp[i]  

            }
        }
        maxLen = max(maxLen, dp[i]);  
    }
    printf("%d", maxLen);  
    return 0;  
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    最长上升子序列的最优方案

    在这里插入图片描述

    在这里插入图片描述

    #include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100;
int a[MAXN];
int dp[MAXN], pre[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    memset(pre, -1, sizeof(pre));
    int k, maxLen = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            k = i;
        }
        maxLen = max(maxLen, dp[i]);
    }
    vector<int> maxLenSeq; 
    while (k != -1) {   
        maxLenSeq.push_back(a[k]);   
        k = pre[k];   
    }
    reverse(maxLenSeq.begin(), maxLenSeq.end());           
    printf("%d\n", maxLen);           
    for (int i = 0; i < maxLenSeq.size(); i++) {            
        printf("%d", maxLenSeq[i]);            
        if (i < (int)maxLenSeq.size() - 1) {            
            printf(" ");            
        }
    }
    return 0;            
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    最长公共子序列(LCS)

    对待这样的题目动态规划的思路是：令dp[i][j]来表示字符串A的i位和字符串B的j号位之前的LCS长度。

    • 若A[i]==B[j],则字符串A与字符串B的LCS增加1位，即有dp[i][j]=dp[i-1][j-1]+1

    • 若A[i]!=B[j]，则A的i号位和B的j号位之前的LCS无法延长。因此 dp[i][j] 就会继承dp[i-1][j]与dp[i][j-1]中的较大值，即有dp[i[j]=max{dp[i-1][j],dp[i][j-1]}

    在这里插入图片描述

    #include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 100 + 1;
int dp[MAXN][MAXN];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    printf("%d", dp[s1.length()][s2.length()]);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 更为详细的解释
    • 补充：边界问题，dp[i][0]=dp[0][j]=0(0<=i<=n,0<=j<=m)
    //补充：边界问题，dp[i][0]=dp[0][j]=0(0<=i<=n,0<=j<=m)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
const A[N], B[N];
int dp[N][N];
int main()
{
    int 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 = 0; i <= lenA; i++)  
    {
        for (int j = 0; j <= lenB; j++)   
        {
            if (A[i] == B[j]) 如果（A[i]==B[日]）     
            {
                dp[i][j] = dp[i - 1][j - 1] + 1; DP[I][J]=DP[I-1][J-1]+1;     
            }
            else 还     
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); dp[i][j]=max（dp[i-1][j]，dp[i][j-1]）;     
            }
        }
    }
    printf("%d", dp[lenA][lenB]); printf（“%d”，dp[lenA][lenB]）;     
 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    最长回文字符串

    解题思路：令dp[i][j]表示s[i]至s[j]所表示的子串是否是回文字符串
    是则是1，不是则是0，这样根据s[i]是否等于s[j],可以将情况为两类
    令dp[i][j]表示s[i]至s[j]所表示的子串是否是回文字符串
    是则是1，不是则是0，这样根据s[i]是否等于s[j], 可以将情况为两类
    1，若s[i] == s[j], 那么只要s[i + 1]至s[j - 1]是回文子串，s[i]至s[j]就是回文子串
    如果不是，那也不是回文子串
    2，若s[i] != s[j], 那么s[i]至s[j]一定不是回文子串

    • 由此可以写出状态转移方程：
    **dp[i][j] = {
    dp[i + 1][j - 1],s[i] = s[j];
    0,s[i]!=s[j]
}**

    • 1
    • 2
    • 3
    • 4
    • 边界：边界：
      dp[i][i]=1,dp[i][i+1]=(s[i]==s[i+1])?1:0
    • 问题=如果按照i和j从小到大的顺序来枚举子串的两个端点
      然后更新d[i][j]无法确定d[i+1][j-1]就已经被计算过
      所以最好的选择就是用：
      根据递推的写法从边界出发原理，按子串的长度和子串的初始位置就行枚举

    左边端点为i，右边端点为i+L-1//L表示子串的长度，也可以是整个字符串的长度

    题目一

    在这里插入图片描述

    #include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 100 + 1;
int dp[MAXN][MAXN]; 

int main() {  
    string s1, s2;  
    cin >> s1 >> s2;  
    for (int i = 1; i <= s1.length(); i++) {  
        for (int j = 1; j <= s2.length(); j++) {  
            if (s1[i - 1] == s2[j - 1]) {  
                dp[i][j] = dp[i - 1][j - 1] + 1;  
            } else {  
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);  
            }
        }
    }
    printf("%d", dp[s1.length()][s2.length()]);  
    return 0;  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    题目二

    给出一个字符串S，求出S的最长回文字符串的长度
    样例：
    字符串"PATZJUJZTACCBC"的最长回文字符串为"ATZJUJZTA"长度为9

    #include<cstdio>
#include<string>
const int N = 1010;
char s[N];
int dp[N][N];
int main()
{
    gets(s);
    int len = strlen(s), ans = 1;
    memset(dp, 9, sizeof(dp));//dp数组的初始化为0

    //边界
    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;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
  • 相关阅读:
    Git - 入门到熟悉_分支管理
    mysql中遇到查询字段的别名与函数冲突问题
    Linux命令
    第7章-查找
    kotlin基础之高阶函数
    架构孪生：架构的数字化形态？？？
    诚邀莅临 | 天奥智能参展第86届中国国际医疗器械博览会
    社区分享｜腾讯海外游戏基于JumpServer构建游戏安全运营能力
    python做小游戏之一小迷宫游戏
    YOLO系列 --- YOLOV7算法（四）：YOLO V7算法网络结构解析
  • 原文地址：https://blog.csdn.net/yihoujian_2003/article/details/134548496