什么是动态规划

?概念

动态规划（Dynamic Programming，DP）：用来解决最优化问题的算法思想。

动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。

一般来说，动态规划将复杂的问题分解为若干子问题，通过综合子问题的最优解来得到原问题的最优解。
动态规划会将每个求解过的子问题记录下来，这样下次碰到相同的子问题，就可以直接使用之前记录的结果，而不重复计算。

动态规划的特点

最优子结构：动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。（“分”与“合”体现在状态转移方程）其实有时候用动态规划也不一定就是最优解那种意思。比如斐波拉契数列，我们很难从中体会到最优解的意味。我感觉这句话是在告诉我们：出现最优解的问题的时候，要第一时间想到动态规划，不是最优解的问题时，也要想到动态规划分解子问题的思想！
重叠子问题：动态规划会将每个求解过的子问题的解记录下来，这样当下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。（虽然动态规划使用这种方式来提高计算效率，但不能说这种做法就是动态规划的核心）所谓记录就是dp数组。

动态规划的写法

递归，自顶向下（Top-down Approach），即从目标问题开始，将它分解成子问题的组合，直到分解至边界为至。
递推，自底向上（Bottom-up Approach），即从边界开始，不断向上解决问题，直到解决了目标问题；

适用的场景

适用场景：最大值/最小值, 可不可行, 是不是，方案个数

何时使用动态规划

一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。
为什么呢？就像我们要求一个学校的考试最高分，那么我们可以从把人分为一个个班级，全校的最高分肯定是班级的最高分，我们要求全校的最高分，要从一个个班级中的最高分去选择

核心套路

其核心就是写出其状态转移方程（穷举）

动态规划的本质，是对问题 状态的定义 和 状态转移方程的定义 ( 状态以及状态之间的递推关系 )

还是需要多练，多写，多总结

因为状态转移方程体现了动态规划重叠子问题和最优子结构这两个特性，因此书写状态转移方程是最困难的。下面是从网上学到的一个思维框架，用于辅助思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)
区别

分治和动态规划

共同点：都是将问题分解成子问题，然后合并子问题的解得到原问题。
区别：分治分出来的子问题是不重叠的，如归并排序和快速排序（分别处理左右排序，然后将左右序列结果合并），分治解决的问题不一定是最优化问题。动态规划解决的问题拥有重叠子问题，且一定是最优化问题。

?贪心和动态规划

共同点：都要求问题拥有最优子结构。
贪心：整个过程以单链的流水方式进行，显然这种“最优的选择”的正确性需要用归纳法证明。例如数塔问题，贪心从最上层开始，每次选择左下或右下较大的那个，一直到最底层得到结果，显然这不一定可以得到最优解。
动态规划：无论采用自底向上还是自顶向下的方法，都是从边界向上得到最优解，它总是会考虑所有子问题，并选择继承能得到最优结果那个，对于暂时没被继承的子问题，由于重叠子问题的存在，后期可能会再次考虑它，因此还有机会成为全局最优的一部分，不需要放弃。
?