而如果你没有模拟所有可能,而直接走了一条最优解,那就是贪心算法了。
是不是和分治有点像? 分治指的是将问题一分为多,然后将多个解合并为一。而这里并不是这个意思。
递归在函数式编程中地位很高。 纯粹的函数式编程中没有循环,只有递归。
满足这两个条件有什么用呢?这是因为我们需要函数给定参数,其返回值也是确定的。这样我们才能记忆化。关于记忆化,我们后面再讲。
到第 n - 1 级台阶的数目加上到第 n - 2 级台阶的数目
。key 的形式为 (x, y),表示的是一个元祖。通常动态规划的参数有多个,我们就可以使用元祖的方式来记忆化。或者也可采取多维数组的形式。对于上图来说,就可使用二维数组来表示。
不将第三件物品装进背包(即仅考虑前两件)
,也就是 f([1,2], [2,2], 10)将第三件物品装进背包
,也就是 f([1,2,3], [2,2,4], 10) (即仅考虑前两件的情况下装满容量为 10 - 3 = 7 的背包) 等价于 4 + f([1,2], [2,2], 7),其中 4 为第三件物品的价值,7 为装下第三件物品后剩余可用空间,由于我们仅考虑前三件,因此前两件必须装满 10 - 3 = 7 才行。显然这两个问题还是复杂,我们需要进一步拆解。不过,这里不是讲如何拆解的。
s[start:end+1] 指的是包含 s[start],而不包含 s[end+1] 的连续子串。
我说空间复杂度打底是状态个数, 这里暂时先不考虑状态压缩的情况。
上 n - 1 级台阶的数目加上 n - 2 级台阶的数目
。f(n) = f(n - 1) + f(n - 2)
。二维的也是一样的,大家可以试试。
如果需要多个维度枚举,那么记忆化递归内部也可以使用迭代进行枚举,比如最长上升子序列问题。
虚线代表的是查表过程
减 1 是因为存在 0 元的情况。
min(dp[i][j], dp[i-1][j - coins[j]] + 1)
,含义就是: min(不选择 coins[j], 选择 coins[j]) 所需最少的硬币数。amount 表示无解。因为硬币的面额都是正整数,不可能存在一种需要 amount + 1 枚硬币的方案。
dp[i][j - 1]
和 dp[i - coins[j - 1]][j] + 1)
这是一个优化的信号,我们可以将其优化到一维。