动态规划（Dynamic Programming，简称DP）是一种解决问题的有效方法，特别适用于具有重叠子问题的情况。

与贪心算法不同，动态规划中的每个状态都是由前一个状态推导出来的。举例来说，背包问题是一个典型的动态规划问题。在背包问题中，每个物品只能使用一次，因此动态规划中的dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

动态规划的解题步骤可以分为五步曲：

1. 确定状态变量dp以及dp的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

在解决动态规划问题时，递推公式是重要的一部分，但并不是唯一的关键。除了递推公式外，还需要考虑dp数组的初始化和遍历顺序。

在动态规划中，状态变量dp的含义至关重要。理解dp数组代表着什么，对于掌握题目至关重要。

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

写动态规划题目时，代码出问题是很正常的。解决问题的最好方式是将dp数组打印出来，看看是否按照自己的思路推导。

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

这一篇是动态规划的整体概述，讲解了什么是动态规划，动态规划的解题步骤，以及如何debug。动态规划是一个很大的领域，今天这一篇讲解的内容是整个动态规划系列中都会使用到的一些理论基础。

在后序讲解中针对某一具体问题，还会讲解其对应的理论基础，例如背包问题中的01背包，leetcode上的题目都是01背包的应用，而没有纯01背包的问题，那么就需要在把对应的理论知识讲解一下。

我在后面也会更新很多关于动态规划的经典题型以及解题方法。

注明：本篇文章借鉴了作者代码随想录的思路以及部分文章原文，要想深入了解，可以移步原作者的文章：代码随想录 (programmercarl.com)