动态规划

1. Dotcpp
2. 动态规划

什么是线性DP?

一、什么是线性?越是基础的概念，越应该有一个透彻的理解，才能对上层问题有直接了当的理解。比如对线性分割器，你对线性有透彻的理解，一看这个名字就大概知道它是怎么回事了。1.几何理解：线性关系就是直线关系现在你可以想象一条曲线S，它可以是直的也可以是弯的，

动态规划 2022年03月10日 163 点赞 0 评论 84252 浏览

计数DP实例讲解

本篇主要从计数DP上结合实例分析。一、计数类DP——整数划分整数划分大体上可以分为3类（1）考虑顺序的拆分方案（即1，1，2；和2，1，1是两种不同的方案），这种问题一般转化为完全背包即可解决。（2）不考虑顺序的拆分方案，可以划分出空集（也就是可以有对拆分完全没贡献的东西存在（0））（3）不考虑顺序的

动态规划 2022年04月04日 98 点赞 0 评论 61681 浏览

DAG上的DP实例讲解

DAG是学习动态规划的基础，（DAG：有向无环图。）很多问题都可以直接转化为DAG上的最长路、最短路或路径计数问题。两个经典的DAG模型，嵌套矩形和硬币问题。一、嵌套矩形（1）第一个DAG模型：矩形嵌套问题描述：有n个矩形，每个矩形可以用a,b来描述，表示长和宽。

动态规划 2022年02月09日 193 点赞 0 评论 90598 浏览

数位DP概念和实例讲解

说到数位DP，它主要是用于处理一些与数位有关的问题，主要是计数问题。并且数位DP一直以来是DP家族里比较冷门的一种，但一旦遇上了，如果不会数位DP单纯靠暴力方法很难骗分。一、什么是数位DP？数位DP是一种计数用的DP，一般就是要统计一个区间[l,r]内满足一些条件数的个数。

动态规划 2022年03月11日 91 点赞 0 评论 104293 浏览

什么是动态规划?

谈到动态规划，很多人会疑惑动态规划难吗？说实话很难，特别是对于初学者来说，入门动态规划的时候，举个例子，看0-1背包问题，很容易就被题目弄懵了。就算看的懂答案，但就是自己不会做，不知道怎么下手。就像做递归的题，看的懂答案，但下不了手。对于动态规划，

动态规划 2022年04月03日 222 点赞 0 评论 88224 浏览

什么是概率DP？

一、概率DP顾名思义，概率DP就是动态规划求概率的问题。一般来说，我们将dp数组存放的数据定义为到达此状态的概率，那么我们初值设置就是所有初始状态概率为1，最终答案就是终末状态dp值了。我们在进行状态转移时，是从初始状态向终末状态顺推，转移方程中大致思路是按照当前状态去往不同状态的位置概率转移更新DP

动态规划 2022年01月05日 170 点赞 0 评论 94643 浏览

线性DP图文实例讲解

线性DP，所谓线性DP，就是指我们的递归方程有一个明显的线性关系的，有可能是一维线性的，也可能是二维线性的。例题一：大盗阿福题目：阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有NN家店铺，每家店中都有一些现金。

动态规划 2022年02月22日 52 点赞 0 评论 82613 浏览

树形DP概念和实例讲解

一、什么是树型动态规划顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：（1）叶－>根：在回溯的时候从叶子节点往

动态规划 2022年02月06日 249 点赞 0 评论 96016 浏览

什么是状态压缩DP？

状态压缩DP一般是基于二进制进行的。状态压缩DP一般分为两类：①基于连通性DP（棋盘式）②集合式（表示每一个元素是否在集合中）一、概述1.状态压缩状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。

动态规划 2022年05月27日 148 点赞 0 评论 77878 浏览

动态规划概念和实例讲解

动态规划（Dynamicprogramming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划 2022年01月11日 163 点赞 0 评论 101343 浏览