首页 > 其他分享 >DP小秘诀

DP小秘诀

时间:2024-01-25 20:23:56浏览次数:19  
标签:状态 秘诀 问题 DP 动态 规划 dp

动态规划问题的小秘籍

1、动态规划的基本思想:将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

2、适用动态规划的条件:

最优子结构

子问题重叠

无后效性

3、分析动态规划必须分析的三个基本要素:

阶段、状态、决策

比如:“黑熊过河”

阶段:石墩

状态:dp[i]:记录到达第i个石墩剩余能量的最大值。

决策:dp[i]=max{ dp[i-1], dp[i-2]}-q+a[i];
且 max{ dp[i-1], dp[i-2]}-q>=0

找状态转移方程的秘决:

找当前状态从哪里来的(上一个状态)。

4、注意事项

动态规划编程实现时用的是表格法,所以要注意赋初始值(递推的起点)。

标签:状态,秘诀,问题,DP,动态,规划,dp
From: https://www.cnblogs.com/RTER/p/17988084

相关文章

  • TCP与UDP协议的区别以及原理
    网络(11):TCP与UDP协议的区别以及原理TCP和UDP协议的区别以及原理最近重新认知了一下TCP和UDP的原理以及区别,做一个简单的总结。一、作用首先,tcp和udp都是工作在传输层,用于程序之间传输数据的。数据一般包含:文件类型,视频类型,jpg图片等。二、区别TCP是基于连接的,而UDP是基于非连接......
  • 开发WordPress主题和插件,如果调试。
    来源:https://www.shanhubei.com/archives/11789.html开发WordPress主题和插件,如果调试。一、使用自带,设置一下:wp-config.php文件中添加一行代码以打开调试模式define('WP_DEBUG',true);//启用调试日志记录到/wp-content/debug.log文件define('WP_DEBUG_LOG',true......
  • 计网笔记:python实现简单的UDP/TCP代码
    初学计网,同时也是第一次写blog,若有不妥之处请多多包涵......
  • 100 DP
    NO临时剪贴板-1.23P1103书本整理题目简化给定一个数列,和一个数字k,有k次机会将数列中的数字减一。求相邻差值之和最少。其实如果考虑扔掉k本书,操作起来感觉非常的麻烦。如果考虑留下(n-k)书,再求差值是否会更简便呢?f[i][j]=min(f[i][j],f[k][j-1]+abs(a[i]-a[k]));考虑如何排......
  • 动态规划之背包DP
    2024-1-24首先是完全背包和0-1背包:同样是限制空间容量最大为m,然后有n类物品,两者的区别在于:①完全背包中每一类物品有ki个,而0-1背包中每类物品只有1个。②实现上完全背包是正序循环的,而0-1背包是逆序循环的,因为前者需要考虑装多个物品的情况(这个从转移方程可......
  • CF467C George and Job 题解 DP 前缀和
    DP前缀和题目链接题意:给你一个长度为\(n\)的序列,让你从这个序列中挑选出\(k\)个长度为\(m\)的区间,并且任意区间不相交。使得选出的数之和最大,求出这个数。解法:很经典的DP模型,我们定义\(f_{i,j}\)表示从前\(i\)个数选出了\(j\)个区间可以取得的最大值,那么答案为:\(f_{n,k}\)。......
  • Etsy注册须知:从细节到成功,避免被封号的秘诀
    Etsy,一个备受手工制品和创意卖家青睐的平台,吸引了无数想要开启跨境电商之旅的朋友们。然而,对于新手来说,Etsy的注册过程可能充满了挑战。本文将为你揭示Etsy注册的关键细节,助你顺利开店,避免被封号的风险。首先,让我们来看看Etsy注册过程中常见的一些问题。有些朋友在第一步输入邮箱后......
  • CF-431-D-二分+数位DP
    431-D题目大意请你找到一个数\(n\),满足区间\([n+1,2n]\)中恰有\(m\)个数的二进制表示中有\(k\)个\(1\)。Solution这种区间中计数类型的题目首先相当数位DP。但是这里缺乏上下界,难点就在于观察到\(n\)的单调性(\([n+1,2n]\)中有\(k\)个\(1\)的数是单调不减的),简要证明:对于......
  • CDP技术系列(三):百万级QPS的人群命中服务接口性能优化指南
    一、背景介绍CDP系统提供了强大的标签和群体的构建能力,面对海量数据的标签和群体,我们采用了Bitmap+ClickHouse的存储与计算方案。详细内容可以参考之前文章。有了群体之后,它们被广泛的应用到支付,消金,财富,营销等各种核心业务的用户拉新,交易转化,促活等核心链路中。而人群应用方式......
  • CDP技术系列(三):百万级QPS的人群命中服务接口性能优化指南
    一、背景介绍CDP系统提供了强大的标签和群体的构建能力,面对海量数据的标签和群体,我们采用了Bitmap+ClickHouse的存储与计算方案。详细内容可以参考之前文章。有了群体之后,它们被广泛的应用到支付,消金,财富,营销等各种核心业务的用户拉新,交易转化,促活等核心链路中。而人群应用方式中,基......