动态规划做多了以后，总结的相关知识

向右看齐 2023-07-01 05:25 4阅读 0赞

# 动态规划 Dynamic Programming DP #

![20200119123254622.png][]

## 准则 ##

**动态规划的本质，是对问题状态的定义和状态转移方程的定义。**

**动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。**

**如何拆分问题，才是动态规划的核心。**

**而拆分问题，靠的就是状态的定义和状态转移方程的定义。**

以LIS为例，重新定义这个问题：

给定一个数列，长度为N，

设F\_\{k\}为：以数列中第k项结尾的最长上升子序列的长度.

求F\_\{1\}..F\_\{N\} 中的最大值.

对于F\_\{k\}来讲，F\_\{1\} .. F\_\{k-1\}都是F\_\{k\}的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第1..k-1中某项结尾的LIS。

上述的新问题F\_\{k\}也可以叫做状态，定义中的“F\_\{k\}为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。

之所以把F\_\{k\}做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。

上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。

比如，对于LIS问题，状态转移方程为：![2020011912324312.png][]

以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。

### a. “缓存”，“重叠子问题”，“记忆化” ###

这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。

### b. “自上而下”，“自下而上” ###

**“递归”**：递归是递推式求解的方法，连技巧都算不上。

怎么实现dp？答：两种常用的方法。（仅仅涉及一般问题）

1. 自下而上：通过正向的loop，求出所有状态对应的值，然后找出max或者min。 优缺点：速度慢，但是相对节省空间。

2. 自上而下：通过递归的方法，需要求解f(x)，则必须知道f(y)，要知道f(y)，必须求f(z). 优缺点：速度快，只用算需要的值，但是要调用堆栈，浪费空间。

### c. "无后效性"，“最优子结构” ###

上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。

**每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到**

**这个性质叫做最优子结构；**

**而不管之前这个状态是如何得到的**

**这个性质叫做无后效性。**

在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。

### d. 关于复杂度的分析 ###

时间复杂度O （状态数 \* 每个状态下所对应的决策数）。

空间复杂度O （状态数）。

[20200119123254622.png]: https://img-blog.csdnimg.cn/20200119123254622.png
[2020011912324312.png]: https://img-blog.csdnimg.cn/2020011912324312.png

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划算法做题思路

文章目录 1. 概念 2. 动态规划常见的类型 3. 动态规划类题目分析思路 1. 概念动态规划（Dynamic Pro

ゞ浴缸里的玫瑰/ 2024年03月22日 15:49/ 0 赞/ 61 阅读

相关动态规划算法——知识点总结

动态规划算法通常用于求解具有最优性质的问题基本概念动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，

Myth丶恋晨/ 2023年10月17日 13:02/ 0 赞/ 124 阅读

相关总结一下动态规划的思路

写在前面我相信只要是接触算法的同学，就一定会接触DP，也就是动态规划，虽然经常遇见动态规划相关的算法题，但是许多人还是有些畏惧，不过我相信只要你愿意静下来学习总结，看看

逃离我推掉我的手/ 2023年07月25日 12:38/ 0 赞/ 11 阅读

相关动态规划做多了以后，总结的相关知识

动态规划 Dynamic Programming DP ![20200119123254622.png][] 准则动态规划的本质，是对问题状态的定义和状态转移方

向右看齐/ 2023年07月01日 05:25/ 0 赞/ 5 阅读

相关动态规划题目总结

题目1：输出描述: 对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。输入例子: 2 7 89 256 7

男娘i/ 2022年09月25日 01:14/ 0 赞/ 200 阅读

相关动态规划刷题总结

题目1：输出描述: 对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。输入例子: 2 7 89 256 7

逃离我推掉我的手/ 2022年09月24日 15:28/ 0 赞/ 219 阅读

相关动态规划算法总结

解题方法：动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动

太过爱你忘了你带给我的痛/ 2022年09月24日 12:15/ 0 赞/ 226 阅读

相关动态规划总结

本文转载自：[风中之炎不盛则灭][Link 1] 本文着重讨论状态是如何表示，以及方程是怎样表示的。当然，还附上关键的，有可能作为模板的代码段。但有的代码的实现是

深碍√TFBOYSˉ_/ 2022年08月11日 07:30/ 0 赞/ 201 阅读

相关 [Leetcode][动态规划]相关题目汇总/分析/总结

题目汇总以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。目前范围：Leetcode前150题动态规划题目一维DP 一维DP需要的就

超、凢脫俗/ 2022年05月27日 08:54/ 0 赞/ 283 阅读

相关 MyBatis 动态 SQL 详解（以后写 SQL 爽多了）

![format_png][] 动态 SQL 是 MyBatis 的强大特性之一。如果你使用过 JDBC 或其它类似的框架，你应该能理解根据不同条件拼接 SQL 语句有多痛苦

向右看齐/ 2021年09月07日 06:14/ 0 赞/ 318 阅读