动态规划

1. Dotcpp
2. 动态规划

树形DP概念和实例讲解

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

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

动态规划概念和实例讲解

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

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

线性DP图文实例讲解

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

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

什么是哈希？

从原理到应用分析什么是哈希？一、什么是哈希？哈希（hash）：将任意长度的输入（关键字），通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值，通常哈希值代表了关键字的存储位置。但是为什么要这样做呢？或者说，

动态规划 2022年02月10日 79 点赞 0 评论 85025 浏览

什么是记忆化搜索？

首先大家要知道，记忆化搜索是动态规划的入门。什么是记忆化搜索？搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，

动态规划 2022年04月30日 77 点赞 0 评论 93026 浏览

动态DP实例讲解

一、简介有一类问题，它可以采用DP解决。但是，如果我们加入区间查询，单点修改甚至区间修改，普通DP望尘莫及。于是，动态DP就应运而生了。二、例题例题一：给定一个长度为n的序列，你需要维护两种操作：①查询一个区间的最大子段和；②单点修改(即将一个位置上的数改成另一个数)Solution首先，

动态规划 2022年02月26日 121 点赞 0 评论 104146 浏览

插头DP图文实例讲解

本篇通过图文解析讲述插头DP的内容，结合前面的状态压缩DP知识，以及前置知识：哈希，方便大家能快速理解。在阐述什么是插头DP之前，我们先了解插头DP有什么用？插头DP是用来解决一类网格图上的连通性问题的强力工具。题目的特征是给定的网格非常小（这个特征类似状压DP）。

动态规划 2022年04月14日 158 点赞 0 评论 70546 浏览

记忆化搜索实例讲解

什么是记忆化搜索？记忆化搜索在本质上，还是动态规划，只是实现方式采用了深度优先搜索的形式，但是它不像深度优先搜索那样重复枚举所有情况，而是把已经计算的子问题保存下来，这样就和动态规划的思想不谋而合了。本篇文章会通过最简单的例子对记忆化搜索进行深入讲解，帮助大家学会什么是记忆化搜索。

动态规划 2022年04月24日 244 点赞 0 评论 79808 浏览

DP优化（一）单调队列/单调栈优化实例讲解

一、什么是单调栈和单调队列？（1）单调栈从名字上就听的出来，单调栈中存放的数据应该是严格单调有序的，具有以下两个性质。1.满足从栈顶到栈底的元素具有严格的单调递增或单调递减性；2.满足栈的后进先出特性，即越靠近栈底的元素越早进栈。单调栈也分为单调递增栈和单调递减栈。

动态规划 2022年05月04日 201 点赞 0 评论 128386 浏览

计数DP实例讲解

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

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