动态规划理论基础

￡神魔★判官ぃ 2023-10-16 15:48 2阅读 0赞

#### 动态规划理论基础 ####

*  刷题大纲
 *  动态规划的定义
 *  动态规划的解题步骤
 *   *  动态规划五部曲
 *  动态规划应该如何debug

## 刷题大纲 ##

![在这里插入图片描述][790895e91c134cbd994e36d3ad18b771.png]

## 动态规划的定义 ##

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

在 **关于贪心算法，你该了解这些** 中我举了一个背包问题的例子。

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp\[j\]是由dp\[j-weight\[i\]\]推导出来的，然后取max(dp\[j\], dp\[j - weight\[i\]\] + value\[i\])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

**其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。**

而且很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。

大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。

上述提到的背包问题，后序会详细讲解。

## 动态规划的解题步骤 ##

做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp\[i\]表示的是什么。

**这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中**。

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

### 动态规划五部曲 ###

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

一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？

**因为一些情况是递推公式决定了dp数组要如何初始化！**

后面的讲解中我都是围绕着这五点来进行讲解。

可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题目就解出来了。

其实 确定递推公式 仅仅是解题里的一步而已！

一些同学知道递推公式，但搞不清楚dp数组应该如何初始化，或者正确的遍历顺序，以至于记下来公式，但写的程序怎么改都通过不了。

后序的讲解的大家就会慢慢感受到这五步的重要性了。

## 动态规划应该如何debug ##

通过把dp数组打印出来来debug。

主要思考问题：

1.  这道题目我举例推导状态转移公式了么？
2.  我打印dp数组的日志了么？
3.  打印出来了dp数组和我想的一样么？

**参考资料**：[代码随想录-动态规划理论基础][-]

[790895e91c134cbd994e36d3ad18b771.png]: https://img-blog.csdnimg.cn/790895e91c134cbd994e36d3ad18b771.png
[-]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

发表评论取消回复

表情：

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

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

相关阅读

相关【算法专题】动态规划的理论与实战

在前面的文章中，我们介绍了贪心算法，它们和动态规划一样，通常都可以用来解决多阶段决策最优解的问题。但是在一些场景下，使用它们的话，并不能解决或者不能很好地解决这种多阶段决...

男娘i/ 2024年05月06日 09:43/ 0 赞/ 54 阅读

相关动态规划基础入门【1】

动态规划基础入门 1 基础概念 2 经典题目 > 诀窍：常规递归 -> 缓存表 -> 动态规划 > 需要有一个尝试的过程 2.1 机器人走的方法数

╰+哭是因爲堅強的太久メ/ 2024年04月07日 12:50/ 0 赞/ 71 阅读

相关动态规划理论基础

什么是动态规划 -------------------- 动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是

川长思鸟来/ 2024年03月27日 14:29/ 0 赞/ 70 阅读

相关动态规划：完全背包理论基础

动态规划：完全背包理论基础完全背包总结代码实现完全背包有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i

川长思鸟来/ 2023年10月16日 16:42/ 0 赞/ 33 阅读

相关动态规划理论基础

动态规划理论基础刷题大纲动态规划的定义动态规划的解题步骤动态规划五部曲动态规划应该如何debug 刷题大纲 ![在这

￡神魔★判官ぃ/ 2023年10月16日 15:48/ 0 赞/ 3 阅读

相关【动态规划】——理论基础,经典例题1

> 前言 > > 小亭子正在努力的学习编程，接下来将开启算法的学习~~ > > 分享的文章都是学习的笔记和感悟，如有不妥之处希望大佬们批评指正~~ > > 同

绝地灬酷狼/ 2023年09月27日 17:17/ 0 赞/ 135 阅读

相关算法基础之动态规划

算法基础之动态规划（C++示例）动态规划（Dynamic Programming）指的是通过把一个问题递归拆解成更加简单的子问题的方式简化一个复杂问题。在计算机科学中，

迈不过友情╰/ 2022年09月07日 12:07/ 0 赞/ 206 阅读

相关算法基础--动态规划（笔试记录）

include<iostream> using namespace std; int main() { //输入部分

蔚落/ 2022年05月08日 05:52/ 0 赞/ 157 阅读

相关动态规划基础水题提纲

提纲汉诺塔汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根[金刚石][Link 1]柱子，在一根柱子上从下往上按照大小顺序

灰太狼/ 2022年04月22日 11:02/ 0 赞/ 140 阅读

相关第9章动态规划基础

第9章动态规划基础很多同学听到“动态规划”的名称可能会望而生畏，觉得动态规划的问题都很复杂。但其实，动态规划本质依然是递归算法，只不过是满足特定条件的递归算法。

喜欢ヅ旅行/ 2022年04月11日 12:15/ 0 赞/ 211 阅读