关于动态规划问题的一些想法。

[zyune]

https://labuladong.github.io/algo/3/24/70/ 强烈推荐这个网站 https://www.bilibili.com/video/BV1XV411Y7oE

动态规划问题的特性property是重叠子问题和最优子结构。也就说 一个问题具有 重叠子问题和最优子结构这两个特性，可以判断他是一个动态规划问题。但是一个动态规划问题的核心 仍然是，状态转移方程 即。只有列出正确的「状态转移方程」，才能正确地穷举。

下面是一些简单的解题框架模板和例子

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

动态规划一定是会让你去求最值的，所以说斐波那契数列其实不是一个严格意义的动态规划问题。 但斐波那契数列 可以让你去了解一下什么是最优子结构

[zyune]

为啥叫「状态转移方程」？其实就是为了听起来高端。

f(n) 的函数参数会不断变化，所以你把参数 n 想做一个状态，这个状态 n 是由状态 n - 1 和状态 n - 2 转移（相加）而来，这就叫状态转移，仅此而已。

你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。

可见列出「状态转移方程」的重要性，它是解决问题的核心，而且很容易发现，其实状态转移方程直接代表着暴力解法。

[zyune]

Memorization

有memo的动态规划基本一定是recursion的做法。我觉得这种题目，可以用recursion tree的方法来帮助一下理解。这种一般会比较好想。 EX ，在change coin中 只有1元，2元和5元 面值的硬币供选择，找出给出amount的最少货币枚数。递归树如下 图1

图二

在图1的方框中 的数 其实就是一次递归调用原方程时，所传入的一个参数

O(递归算法的时间复杂度)=递归函数调用的次数*递归函数本身的复杂度 递归函数调用的次数=递归树中的所有节点个数

使用memo{} hashtable的意义是什么： 以下例子是 fib数组中的

把树形的结构转换成了一个链式的结构，每个节点只会出现一次，因为备忘录可以保证有重复节点出现的时候，不会重新计算，所以每个节点只会被计算一次。这个时候，递归函数调用的次数和n输入的大小是成正比的。这个时候的弊端是 空间复杂度增加了，因为备忘录是n的空间复杂度。

细节问题：为什么memo这个hashtable 初始化大小是N+1？

因为数组是0开始的，如果只初始化N 那里面 其实是0 到N-1个 。

[zyune]

迭代算法的好处就是 空间复杂度有可能可以进一步优化

[zyune]

什么是状态，在tabulation中，状态是dp数组的索引，在memorization中，状态是传入的参数