动态规划：线性DP-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划：线性DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数字三角形：

#include<iostream>
using namespace std;

const int N=510,INF=0x3f3f3f3f;
int f[N][N];//存路径长度
int a[N][N];//存数字

int main()
{
    int n;
    scanf("%d",&n);

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

    //为何j从0开始，i+1结束：因为下面的max算的时候，三角形最左的位置(j=1)没有左上角，需要j=0的值
    for(int i=1;i<=n;i++)
    {                        
        for(int j=0;j<=i+1;j++)//三角形最右的位置(j=i)没有右上角，需要i+1的位置
        {
            f[i][j]=-INF;//所有值初始化为负无穷
        }
    }

    f[1][1]=a[1][1];//走到第一个点的长度为a[1][1]
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {   //走到ij的长度加前一个点的长度
            f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);//判断左上和右上哪个更大，题目要求最大路径
        }
    }

    int res=-INF;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);//寻找存的最大路径长度
    printf("%d\n",res);
}

最长上升子序列 I：

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N];//存数字
int f[N];//存路径长度

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

    for (int i = 0; i < n; i++) //以i号数字结尾
    {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j]) 
            {
                f[i] = max(f[i], f[j] + 1);//前一个小于自己的数结尾的最大上升子序列加上自己，即+1
                //这里为何用max而不直接用fj+1，题目没说连续序列，比如：1 3 9 8，8可以由1+3+8也可以9+8，而后判断的9+8是比1+3+8小的
            }
        }
    }
    
    int k=1;
    for(int i=0;i<n;i++)//找最长路径
    {
        if(f[k]<f[i])
        k=i;
    }   
    
    printf("%d\n",f[k]);//输出最长长度
    
    return 0;
}

最长上升子序列 II：

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

const int N=1e5+10;
int arr[N];

int main() 
{
    int n; 
    scanf("%d",&n);

    for (int i = 0; i < n; ++i)scanf("%d",&arr[i]);

    vector<int>stk;//模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; i++) 
    {
        if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
            stk.push_back(arr[i]);
        else//替换掉第一个大于或者等于这个数字的那个数
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }
    printf("%d\n",stk.size());
    return 0;
}
/*
例 n: 7
arr : 3 1 2 1 8 5 6

stk : 3

1 比 3 小
stk : 1

2 比 1 大
stk : 1 2

1 比 2 小
stk : 1 2

8 比 2 大
stk : 1 2 8

5 比 8 小
stk : 1 2 5

6 比 5 大
stk : 1 2 5 6

stk 的长度就是最长递增子序列的长度
*/

最长公共子序列;

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];//a是第一个字符串,b是第二个字符串
int f[N][N];//f存的是状态，即长度

int main()
{
    scanf("%d%d",&n,&m);//a和b的长度
    cin>>a+1>>b+1;//从下标1开始存字符串
  
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j]) //如果ai和bj相同，赋予[i-1,j-1]+1的长度
            {
                f[i][j] = f[i - 1][j - 1] + 1;
            } 
            else //如果不相同，比较[i-1，j]和[i,j-1]的长度并赋给ij。
            {    //其实就是让上一个相同字符串的长度赋给现在，因为是i在外j在内，所以一直是用i,j-1来赋给ij，但是当j==m时，j又回到1，此时的上一个状态就不是i,j-1了，而是i-1,j
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

最短编辑距离:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int m, n;
char a[N],b[N];//两个字符串
int dp[N][N];//所有把a中的前i个字母 变成 b中前j个字母的集合的操作次数。前面是a，后面是b

int main()
{
    scanf("%d%s", &m,a+1);
    scanf("%d%s", &n,b+1);

    //预处理
    for(int i = 0; i <= m; i++) dp[i][0] = i;  //全删除,b的第0个比较a的第i个，则说明删除i次了
    for(int i = 0; i <= n; i++) dp[0][i] = i;  //全插入,a的第0个比较b的第i个，则说明插入i次了

    for(int i = 1; i <=m; i++)
        for(int j = 1; j <=n; j++)
        {
            dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1;//先进行删除操作和添加操作
            if(a[i]==b[j]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);//若该字符相等，则次数与上次相等
            else dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);//若该字符不相等，则判断添加删除操作后的操作数与上一字符的操作数+1比较大小
        }

    printf("%d\n",dp[m][n]);

    return 0;
}

编辑距离:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e1 + 5, M = 1e3 + 10;

int n, m;
char str[M][N];//字符串数组，前面是字符串个数，后面是字符串
int dp[N][N];

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);//从1号位置计算字符串长度
     //预处理，因为后面用得到0号位，所以从0开始
    for(int i = 0; i <= la; i++) dp[i][0] = i;  //全删除,b的第0个比较a的第i个，则说明删除i次了
    for(int i = 0; i <= lb; i++) dp[0][i] = i;  //全插入,a的第0个比较b的第i个，则说明插入i次了

    for(int i = 1; i <=la; i++)
        for(int j = 1; j <=lb; j++)
        {
            dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1;//删除操作和添加操作
            if(a[i]==b[j]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);//若该字符相等，则判断+1
            else dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);//若该字符不相等，则判断添加删除操作后的操作数与上一字符的操作数+1比较大小
        }
        
    return dp[la][lb];//因为从0开始的，所以lalb就是最后一个
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) cin>>str[i]+1;//输入n个字符串

    while (m--) 
    {
        int res = 0;
        char s[N];//给定字符串
        int limit;//限制步骤数
        cin >> (s + 1) >> limit;
        for (int i = 1; i <= n; i++) 
        {
            if (edit_distance(str[i], s) <= limit)//判断该字符串是否可以变成给定字符串
            {
                res++;
            }
        }
        printf("%d\n",res);
    }

    return 0;
}

文章来源地址https://www.toymoban.com/news/detail-736298.html

到了这里，关于动态规划：线性DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！