- 动态规划是一种常用的优化算法的技术，是一种解决最优解问题的方法。
- 由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。
- 这篇文章主要介绍DP的一些基本思想，各种类型问题中DP数组的建立方法，以及一些DP的优化技巧。
概念
- 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。
- 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
- 一个问题的最优解包含其子问题的最优解，这个性质被称为最优子结构性质。
- 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次(overlap problem)。这种性质称为子问题的重叠性质。
- 已经求解的子问题，不会再受到后续决策的影响，这个性质被称为无后效性行性质。
- 满足下面三个条件之一, 则极有可能是使用动态规划求解的：
- 求最大值最小值
- 判断是否可行
- 统计方案个数
关于动态规划的学习资源
- 入门推荐灯神的DP入门视频，讲解十分通俗易懂，我阿嫲一听就会。
- dd大佬的《背包九讲》，是一个非常好的学习背包相关动态规划的资料，几乎涵盖了背包问题的所有内容。
- labuladong 的算法笔记之动态规划解题套路框架。
- 概念学会就可以开启实战了动态规划入门50题，LeetCode Study Plan等。
动态规划解题五步曲
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组