动态规划 - 从记忆化搜索到递推

来源：基础算法精讲 by 灵茶山艾府

视频精讲：动态规划 - 从记忆化搜索到递推

题意与示例

198. 打家劫舍

题目链接：不能同时选择相邻房屋，求可偷取金额的最大总和。

示例：输入 nums = [1,2,3,1]，输出 4。

70. 爬楼梯

题目链接：每次走 1 或 2 阶，统计到达第 n 阶的不同方法数。

示例：输入 n = 2，输出 2。

746. 使用最小花费爬楼梯

题目链接：每次支付当前台阶费用后可走 1 或 2 阶，求到达楼顶的最低花费。

示例：输入 cost = [10,15,20]，输出 15。

3693. 爬楼梯 II

题目链接：每次可向上跳 1 至 3 阶并支付目标台阶费用与跳跃距离平方，求到达第 n 阶的最低总成本。

示例：输入 n = 4, costs = [1,2,3,4]，输出 13。

377. 组合总和 Ⅳ

题目链接：从不同整数中重复选数并考虑排列顺序，统计总和为 target 的方案数。

示例：输入 nums = [1,2,3], target = 4，输出 7。

2466. 统计构造好字符串的方案数

题目链接：从空串开始追加指定长度的 0 或 1，统计长度位于 [low, high] 的不同字符串数量。

示例：输入 low = 3, high = 3, zero = 1, one = 1，输出 8。

2266. 统计打字方案数

题目链接：根据手机按键的连续按压字符串，统计可能对应的文字消息数量。

示例：输入 pressedKeys = "22233"，输出 8。

213. 打家劫舍 II

题目链接：房屋首尾相邻围成一圈，求不偷相邻房屋时可获得的最大金额。

示例：输入 nums = [2,3,2]，输出 3。

64. 最小路径和

题目链接：从网格左上角出发且每次只能向右或向下，求到右下角的最小路径和。

示例：输入 grid = [[1,3,1],[1,5,1],[4,2,1]]，输出 7。