• 欢迎光临~

动态规划算法

开发技术 开发技术 2022-12-26 次浏览

动态规划

基本概念

阶段

问题的过程被分成若干相互联系的部分,我们成为阶段,以便按一定的次序求解。

状态

某一阶段的出发位置成为状态,通常一个阶段包含若干状态。

决策

对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发,通过一次选择性的状态。

基本思想

建立子问题的描述,建立状态间的转移关系,使用递推记忆化搜索法来实现。

  • 状态定义用问题的某些特征参数描述一个子问题。在很多时候,状态描述的细微差别将会引起算法的不同。
  • 状态转移方程即状态值之间的递推关系。这个方程通常需要考虑两个部分:一是递推的顺序,二是递归边界(也是递推起点)
  • 重叠子问题是动态规划展示威力的关键。
  • 能用动态规划的求最优解问题,必须满足最优解的每个局部也都是最优的
  • 无后效性:未来与过去无关

动态规划算法

典型例题

LCS

P1439 【模板】最长公共子序列

最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的.

《算法竞赛进阶指南》上没有给出标程怎么会要标程呢所以给出程序或许并非最佳

  • 状态表示:f[i]表示以a[i]为结尾的“最长上升子序列”的长度

  • 阶段划分:子序列的结尾位置

  • 转移方程

    [f[i]=max(f[j]+1),0<=j<i,a[j]<a[i] ]

  • 边界:f[0]=0

模板代码

    //最长公共子序列
    #include<bits/stdc++.h>
    using namespace std;
    char a[100000],b[100000];
    int dp[10000][10000],n;	//dp为转移数组
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)	cin>>a[i];
        for(int i=1;i<=n;i++)	cin>>b[i];
        dp[n][0]=0,dp[0][n]=0;	//初始化
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);	//状态转移方程
                if(a[i]==b[j])	dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
            }
        }
        printf("%d",dp[n][n]);
        return 0;

LIS

最长上升子序列(Longest Increasing Subsequence),简称LIS,也有些情况求的是最长非降序子序列,二者区别就是序列中是否可以有相等的数。

《算法竞赛进阶指南》上依旧没有给出标程怎么会要标程呢所以给出程序或许并非最佳

  • 状态表示:f[i,j]表示前缀子串a[1-i]与b[1-j]的“最长公共子序列”的长度

  • 状态划分:已处理的前缀长度

  • 转移方程

    [f[i,j]=max(max(f[i-1,j],f[i,j-1]),f[i-1,j-1])\ if(a[i]==b[i]) ]

  • 边界:f[i,0]=f[0,j]=0

模板代码:

    //最长上升子序列
    #include<bits/stdc++.h>
    using namespace std;
    int a[100000],n,dp[100000],ans;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
        dp[0]=0;	//初始化
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(a[j]<a[i])	dp[i]=max(dp[i],dp[j]+1);	//状态转移
            }
        }
        for(int i=1;i<=n;i++)	ans=max(ans,dp[i]);
        printf("%d",ans);
        return 0;
    }

P1434滑雪

详见另一篇博客(更好的阅读体验)~~~

P2196挖地雷

详见另一篇博客(更好的阅读体验)~~~

程序员灯塔
转载请注明原文链接:动态规划算法
喜欢 (0)