动态规划理论基础

川长思鸟来 2024-03-27 14:29 7阅读 0赞

### **什么是动态规划** ###

--------------------

动态规划，英文：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\])。

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

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

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

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

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

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

--------------------

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

**对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！**

1.  确定dp数组（dp table）以及下标的含义

1.  确定递推公式

1.  dp数组如何初始化

1.  确定遍历顺序

1.  举例推导dp数组

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

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

递推公式的重要性确实举足轻重。

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

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

随着对动归的深入接触大家就会慢慢感受到这五步的重要性了。

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

--------------------

写动规题目，代码出问题很正常！

**找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！**

不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，再凭感觉调改bug。

这是一个很不好的习惯！

**做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果**。

然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

**这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了**。

这也是我为什么在动规五步曲里强调推导dp数组的重要性。

有时候代码都已经和题解一模一样了，为什么通过不了呢？

发出这样的问题之前，其实可以自己先思考这三个问题：

*  这道题目我举例推导状态转移公式了么？

*  我打印dp数组的日志了么？

*  打印出来了dp数组和我想的一样么？

**如果这灵魂三问自己都做到了，基本上这道题目也就解决了**，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

### **总结** ###

--------------------

这一篇是动态规划的整体概述，讲解了什么是动态规划，动态规划的解题步骤，以及如何debug。

动态规划是一个很大的领域，这一篇讲解的内容是整个动态规划系列中都会使用到的一些理论基础。

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划理论基础

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

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

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

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

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

相关算法基础之动态规划

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

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

相关动态规划

首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 228 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 224 阅读

相关动态规划

1.题目：最长递增子序列（Longest Increasing Subsequence）问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 194 阅读

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

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

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

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

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

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

相关第9章动态规划基础

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

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

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 377 阅读