动态规划

简介: 动态规划

动态规划是一种用来解决最优化问题的算法思想,其会记录下子问题的最优解,综合子问题的最优解得到最优解。

上面有两个关键,划分子问题和记录子问题,其中划分子问题有一个重要的状态转移方程

一般解决步骤如下:

1.确定维数,确定dp数组。

2.每一维采用下面表述,为i或者前i。

3.之后问题可以描述为dp[i]为恰好为i(或者前i)的XXX(问题描述),然后思考dp[i-1]得出状态转移方程。


动态规划的题目主要可能得多看习题领悟,这里针对典型例题来领悟动态规划的过程。

最大连续子序列和

问题:给定一个序列(整数或浮点数),求出其中连续的子序列和最大的那一个。

例:序列{-10 1 2 3 4 -5 -23 3 7 -21},其最大的连续子序列为{1 2 3 4}或{3 7},最大和为10。


首先涉及到一个序列,应该是一维问题,应该可以用一个一维数组来记录子问题的最优解,第二步dp[i]表述恰好为i时在最大连续和(前i肯定不合适),第三步思考dp[i-1]和dp[i] 的关系,如果dp[i-1]<0,显然dp[i]=a[i],否则加上前面的dp[i-1]dp[i]肯定更大,于是状态转移方程得出。最后问题思考的序列完找出dp[i]最大的即可。


附代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10001;
int dp[maxn],a[maxn];//dp[i] 表示结尾恰好为i时最大和 
int main(){
  int n;
  while(scanf("%d",&n),n){
    fill(dp,dp+n+1,-1);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    int max=-100000,k=-1;
    for(int i=1;i<=n;i++)
    {
      if(dp[i-1]>0)dp[i]=dp[i-1]+a[i];  //状态转移 
      else dp[i]=a[i];
      if(max<dp[i])        //更新最大值 
      {
        max=dp[i];
        k=i;
      }
    }
    if(max<0)printf("%d %d %d\n",0,a[1],a[n]);
    else {
    printf("%d ",max);
    for(int i=k;max!=0||dp[i-1]==0;i--)
    {
      max-=a[i];
      if(max==0&&dp[i-1]!=0)
      printf("%d ",a[i]);
    }
    printf("%d\n",a[k]);
    }
  } 
return 0; 
}

最长上升子序列

问题:给一个数组a1, a2 … an,找到最长的不下降子序列ab1<ab2<=… <abk,其中b1<b2<…bk,输出长度即可。


思考:维度应该一维,dp[i]应该表示以i结尾的最大不下降子序列长度,前面如果数字都比a[i]大那么dp[i]就为1,否则只要前面dp[j]对应a[j]<a[i],且长度+1后比dp[i]长度大,说明a[i]可以接在a[j]后面得到最大长度。


代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5001;
char a[maxn],dp[maxn];
int main(){
  int n,length=0;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  scanf("%d",&a[i]) ;
  fill(dp,dp+n+1,0);
  a[0]=-1;
  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<i;j++) {
      if(a[j]<a[i]&&dp[j]+1>dp[i])
      dp[i]=dp[j]+1;
    }
    if(length<dp[i])length=dp[i];
  }
  printf("%d\n",length);
  return 0;
}

最长公共子序列


问题:给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB

则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA


分析:两个字符串,应该是二维,dp[i][j]应该表示为两个字符串第i,j位之前的最长公共子序列数,如果两个字符串第ij位相等,长度肯定是dp[i-1][j-1]+1,否则应该是dp[i-1][j]或者dp[ii][j-1]中的最大值。


代码如下:

#include<iostream>
#include<algorithm>
#include<string> 
using namespace std;
const int maxn=101;
string a,b;
int dp[maxn][maxn];
int main(){
  while(cin>>a>>b){
  fill(dp[0],dp[0]+maxn*maxn,0);
  int n=a.size(),m=b.size();
  for(int i=1;i<=n;i++){
  for(int j=1;j<=m;j++){
    if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1;
    else {
      if(dp[i][j-1]>dp[i-1][j])
        dp[i][j]=dp[i][j-1];
        else dp[i][j]=dp[i-1][j];
    }
  }
  }
  a.clear();b.clear();
  cout<<dp[n][m]<<endl;}
return 0; 
}

简单取了三个例子,此外还有最长回文子串、dag最长路、背包问题的应用。分别教会了我变换更新方式、递推和递归、打印路径,这里一定多练习。

相关文章
|
域名解析 缓存 网络协议
DNS服务详解
DNS服务详解
1011 0
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1303 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1329 87
|
2天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
183 82
2025年阿里云域名备案流程(新手图文详细流程)