DP | 54 动态规划总结题纲

2023-11-23 14:59
文章标签 动态 规划 总结 dp 54 题纲

本文主要是介绍DP | 54 动态规划总结题纲，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文记录的是刷题过程中的重要概念和笔记。如有侵权，请联系删除。

目录

  • 动规五部曲
  • 背包问题
  • 股票系列
  • 子序列系列
  • 总结

动规五部曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

背包问题

在这里插入图片描述

股票系列

在这里插入图片描述

子序列系列

在这里插入图片描述

总结

关于动规，还有 树形DP（打家劫舍系列里有一道），数位DP，区间DP ，概率型DP，博弈型DP，状态压缩dp等等等，这些我就不去做讲解了，面试中出现的概率非常低。

能把本篇中列举的题目都研究通透的话，你的动规水平就已经非常高了。 对付面试已经足够！在这里插入图片描述

这篇关于DP | 54 动态规划总结题纲的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/418746。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...
usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2