首页 > 其他分享 >动态规划三:常见状态与常见递推关系式

动态规划三:常见状态与常见递推关系式

时间:2023-06-08 14:04:20浏览次数:36  
标签:关系式 常见 循环 dp 区间 长度 递推 最值




动态规划三:常见递推关系式

  • 常见状态
  • 坐标型
  • 前缀划分型
  • 前缀匹配型
  • 区间型
  • 背包型

    动态规划三:常见状态与常见递推关系式_递推关系


    常见状态

    坐标型

    • dp[i]:从起点到坐标 i 的最值/方案数/可行性
    • dp[i][j]:从起点到坐标 i, j 的最值/方案数/可行性
       

    前缀划分型

    • dp[i]:前 i 个字符的最值/方案数/可行性
    • dp[i][j]:前 i 个字符划分为 j 个部分的最值/方案数/可行性
       

    前缀匹配型

    • dp[i][j]:第一个字符串的前 i 个字符匹配上第二个字符串的前 j 个字符的最值/方案数/可行性
       

    区间型

    • dp[i][j]:区间 i-j 的最值/方案数/可行性
       

    背包型

    • dp[i][j]:前 i 个物品里选出一些物品组成和为 j 的大小的最值/方案数/可行性
       

    常见递推关系式

    动态规划虽然飘逸,但还是有规律可循,前人还是总结了好几种常见的递推关系模式。

    动态规划算法有三个要素:

    • 所有不同的子问题所组成的表(它包含的问题数目称为问题的大小,即 size);
    • 问题解决的依赖关系可以看成是一个图;
    • 填充子问题的顺序(实际上就是(2)所得到的图的一个拓扑排序)。

    如果子问题的数目为 动态规划三:常见状态与常见递推关系式_动态规划_02,且每个子问题需要依赖于 动态规划三:常见状态与常见递推关系式_递推关系_03 个其他子问题,则称这个问题为 动态规划三:常见状态与常见递推关系式_字符串_04

    总结起来可得到四种典型的动态规划关系递推方程:动态规划三:常见状态与常见递推关系式_字符串_05动态规划三:常见状态与常见递推关系式_动态规划_06动态规划三:常见状态与常见递推关系式_算法_07动态规划三:常见状态与常见递推关系式_算法_08
     


    动态规划三:常见状态与常见递推关系式_字符串_05

    定义一个实函数 动态规划三:常见状态与常见递推关系式_算法_10,已知 动态规划三:常见状态与常见递推关系式_递推关系_11,状态转移方程:

    • 动态规划三:常见状态与常见递推关系式_字符串_12

    P.S. opt 是最优关系,可能是 max,也可能是 min。

    其中,动态规划三:常见状态与常见递推关系式_算法_13 可以根据 动态规划三:常见状态与常见递推关系式_字符串_14

    《算法导论》里的切分钢条,锯木头问题,最长上升子序列都是这种结构。
     


    动态规划三:常见状态与常见递推关系式_动态规划_06

    已知 动态规划三:常见状态与常见递推关系式_字符串_16动态规划三:常见状态与常见递推关系式_递推关系_17,状态转移方程为:

    • 动态规划三:常见状态与常见递推关系式_递推关系_18

    其中,动态规划三:常见状态与常见递推关系式_字符串_19

    线性DP(如最长公共子序列)、串DP 问题,多是这种结构,具体的理解,您要在行动中来思考。
     


    动态规划三:常见状态与常见递推关系式_算法_07

    定义实函数 动态规划三:常见状态与常见递推关系式_算法_21,已知 动态规划三:常见状态与常见递推关系式_递推关系_22,状态转移方程为:

    • 动态规划三:常见状态与常见递推关系式_字符串_23

    区间动态规划模型多是这种结构。

    区间动态规划,顾名思义,就是求解一个区间内的某种最优解,这种题目在分解子问题的时候,通常考虑子问题就是其中任意一个子区间,而规划的内容就是如何分解子区间。无论题目内容怎样,算法的实现模式基本上就是一个如下所示的三重循环。

    for(区间长度 size:从最小可分区间开始到最大区间长度)
    {
        for(小区间起始位置 i:从第一个位置开始到区间长度 size 所决定的结束位置)
        {
            j = i + szie - 1; // j 定义区间结束位置,具体计算方法因问题而异
            for(区间分割点位置 k:从 i 开始到 j 结束) // 遍历所有区间 [i,j] 内的位置,将其分割为两个小区间
            {
                f[i][j] = max(f[i][j],f[i][k]+f[k][j] + 某种最优值计算方法)
                或
                f[i][j] = min(f[i][j],f[i][k]+f[k][j] + 某种开销计算方法)
            }
        }
    }

    第一重循环枚举区间的大小,一般是从最小可分解区间开始,直到最大区间长度。

    为什么枚举区间长度要从“最小可分解区间”开始呢?

    因为区间长度太小的话,不满足题目的分解区间要求,后续的处理也没有意义。具体的“最小可分解区间”的值,因题而异,比如三角形组合问题,最小区间长度至少是 3 条边才行,否则连一个三角形都凑不齐,后续还怎么处理?对于经典的“石子合并”问题,区间长度就是石子的堆数,要能够合并,至少要 2 堆石子吧,所以石子堆数就从 2 开始枚举。

    实现模式的第二重循环是对区间内的起始位置开始枚举。

    • 第一重循环给定了区间的大小(范围);
    • 第二重循环就尝试从区间的不同位置开始定义子区间。
      举个简单的例子,假设第一重循环给定了区间长度是 5,则第二重循环要处理的最大区间就是 [1,2,3,4,5],第二重循环的作用就是分别尝试定义子区间,共可得到 5 个子区间: [1,2,3,4,5]、[2,3,4,5]、[3,4,5]、[4,5] 和 [5];
    • 第三重循环就是尝试对每个子区间分解,假设前两重循环选择了第二步分解的 5 个子区间中的第 2 个子区间,也就是 [2,3,4,5],则 k 的值就是从 2 到 5,拆分子区间,共得到三组拆分结果:[2] 和 [3,4,5]、[2,3] 和 [4,5]、[2,3,4] 和 [5]。对于每一组拆分结果,计算状态值:
    state1 = f[2][2] + f[3][5] + 根据当前 k=2 的分解得到的某种最优值(或开销值) 
    state2 = f[2][3] + f[4][5] + 根据当前 k=3 的分解得到的某种最优值(或开销值)
    state3 = f[2][4] + f[5][5] + 根据当前 k=4 的分解得到的某种最优值(或开销值)

    而后将三个 state 分别与 动态规划三:常见状态与常见递推关系式_算法_24 比较,根据题目的要求,用最优值更新 动态规划三:常见状态与常见递推关系式_算法_24

    当全部三重循环都完成后,题目要求的解就在 动态规划三:常见状态与常见递推关系式_字符串_26

    这就是区间动态规划的解题思路和实现模板,具体的理解,您要在行动中来思考。
     


    动态规划三:常见状态与常见递推关系式_算法_08

    定义实函数 动态规划三:常见状态与常见递推关系式_字符串_28,已知 动态规划三:常见状态与常见递推关系式_字符串_16动态规划三:常见状态与常见递推关系式_递推关系_30,状态转移方程为:

    • 动态规划三:常见状态与常见递推关系式_动态规划_31

    其中,动态规划三:常见状态与常见递推关系式_算法_32 可以根据 动态规划三:常见状态与常见递推关系式_算法_33

    对于以上四种典型方程,如果方程是 动态规划三:常见状态与常见递推关系式_字符串_04 类型,可以套用上述递推关系式得到一个时间复杂度为 动态规划三:常见状态与常见递推关系式_动态规划_35、空间复杂度 动态规划三:常见状态与常见递推关系式_动态规划_02


    标签:关系式,常见,循环,dp,区间,长度,递推,最值
    From: https://blog.51cto.com/u_13937572/6439497

    相关文章

    • hncloud:常见的美国服务器操作系统
      常见的美国服务器操作系统包括:WindowsServer:WindowsServer是微软公司提供的服务器操作系统,适用于各种企业级应用和服务,如网站托管、数据库管理、应用程序部署等。Linux发行版:Linux是一种开源操作系统,有许多不同的发行版可供选择,包括但不限于以下几种常见的发行版:Ubuntu:一种基于De......
    • P8933 [JRKSJ R7] 技巧性的块速递推 题解
      题目传送门题意:简单来说就是一个涂色游戏。有一个n×m的棋盘需要涂色。每格只能涂黑色或白色两种颜色。横、竖、斜连续3格颜色不能相同。横、竖、斜连续4格颜色不能有3个相同颜色,即只能是2个黑和2个白。最后让你统计出所有符合条件的涂色方式的方......
    • mysql常见的时间查询语句
      mysql数据库要按当天、昨天、前七日、近三十天、季度、年查询查询今天select*from表名whereto_days(时间字段名)=to_days(now());   查询昨天SELECT*FROM表名WHERETO_DAYS(NOW())-TO_DAYS(`时间字段名`)=1 查询7天 sql语句SELECT*FROM表名whereDATE_SUB(CU......
    • 第3天学习Docker-Docker部署常见应用(MySQL、Tomcat、Nginx、Redis、Centos)
      前提须知:(1)搜索镜像命令格式:dockersearch镜像名(2)设置Docker镜像加速器详见文章:Docker设置ustc的镜像源(镜像加速器)1、部署MySQL拉取镜像(这里拉取mysql5.7版本)[root@localhost~]#dockerpullmysql:5.7创建容器(默认运行)[root@localhost~]#dockerrun-di--name=my_mysql-p330......
    • vue常见自定义指令
      常见自定义指令一、响应缩放指令使用<divv-resize="resize"></div>代码/***响应缩放指令*@direction使用该指令可以响应元素宽高改变时执行的方法。*@resize{function}传入对应resize方法*v-resize="resize"**/exportdefault{bind(el,bi......
    • 帮助中心的设计指南:帮助用户快速解决常见问题!
      帮助中心对于用户而言,就是使用手册,一套系统实用的帮助中心可以节约大量的沟通成本,帮助用户快速上手使用该产品。 帮助中心应用方向当下产品帮助中心的应用方向,可以分为两类:一类是给企业内部使用的,一类是给企业外部使用的。但无论是对内还是对外,产品帮助中心的设计都是从产品的基本......
    • 转:使用c#实现23种常见的设计模式
      转自:https://www.cnblogs.com/hejiale010426/archive/2023/06/05/17457761.html设计模式通常分为三个主要类别:创建型模式结构型模式行为型模式这些模式是用于解决常见的对象导向设计问题的最佳实践。以下是23种常见的设计模式并且提供c#代码案例:1.创建型模式1.1单例模......
    • 常见的进程信号
      进程的管理主要是指进程的关闭和重启。我们一般关闭或重启软件,都是关闭或者重启它的程序,而不是直接操作进程的。比如,要重启apache服务,一般使用命令servicehttpdrestart重启apache的程序。那么,可以直接通过管理进程来关闭或重启apache吗?答案是肯定的,这时候就要依赖进程的信号S......
    • (转)常见日志收集方案及相关组件
      原文:https://www.cnblogs.com/hujinzhong/p/15005523.html一、常见日志收集方案1.1、EFK​在Kubernetes集群上运行多个服务和应用程序时,日志收集系统可以帮助你快速分类和分析由Pod生成的大量日志数据。Kubernetes中比较流行的日志收集解决方案是Elasticsearch、Fluentd和Kiba......
    • DataLeap的全链路智能监控报警实践(一):常见问题
      随着字节跳动业务的快速发展,大数据开发场景下需要运维管理的任务越来越多,然而普通的监控系统只支持配置相应任务的监控规则,已经不能完全满足当前需求,在日常运维中开发者经常会面临以下几个问题:任务多,依赖关系复杂:很难查找到重要任务的所有上游任务并进行监控。如果监控所有任务......