爬楼梯：中等
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
1 |
2 |
|
输入 |
n = 2 |
n = 3 |
输出 |
2 |
3 |
解释 |
有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 |
有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 |
解题思路：
设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
1. 当为 1 级台阶： 剩 n−1 个台阶，此情况共有 f(n−1) 种跳法。
2. 当为 2 级台阶： 剩 n−2 个台阶，此情况共有 f(n−2) 种跳法。
即 f(n) 为以上两种情况之和，即 f(n)=f(n−1)+f(n−2) ，以上递推性质为斐波那契数列。因此，本题可转化为 求斐波那契数列的第 n 项，区别仅在于初始值不同：
·青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 。
·斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。
动态规划解析：
·状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列的第 i 个数字。
·转移方程： dp[i+1]=dp[i]+dp[i−1] ，即对应数列定义 f(n+1)=f(n)+f(n−1) 。
·初始状态： dp[0]=1, dp[1]=1 ，即初始化前两个数字。
·返回值： dp[n] ，即斐波那契数列的第 n 个数字。
状态压缩：
若新建长度为 n 的 dp 列表，则空间复杂度为 O(N) 。
由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum 使 a,b 两数字交替前进即可 （具体实现见代码） 。由于省去了 dp 列表空间，因此空间复杂度降至 O(1) 。
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
复杂度分析：
·时间复杂度 O(n) ： 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。
·空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。
杨辉三角：简单
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
解题
把杨辉三角的每一排左对齐：
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
设要计算的二维数组是 c，计算方法如下：
·每一排的第一个数和最后一个数都是 1，即 c[i][0]=c[i][i]=1。
·其余数字，等于左上方的数，加上正上方的数，即 c[i][j]=c[i−1][j−1]+c[i−1][j]。例如 4=1+3, 6=3+3 等。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
c = [[1] * (i + 1) for i in range(numRows)]
for i in range(2, numRows):
for j in range(1, i):
# 左上方的数 + 正上方的数
c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
return c
复杂度分析
- 时间复杂度：O(numRows2)。
- 空间复杂度：O(1)。返回值不计入。
如何理解这个式子
递推式
c[i][j]=c[i−1][j−1]+c[i−1][j]
本质上是一个组合数恒等式，其中 c[i][j] 表示从 i 个不同物品中选出 j 个物品的方案数。
如何理解上式呢？考虑其中某个物品选或不选：
·选：问题变成从剩下 i−1 个不同物品中选出 j−1 个物品的方案数，即 c[i−1][j−1]。
·不选：问题变成从剩下 i−1 个不同物品中选出 j 个物品的方案数，即 c[i−1][j]。
二者相加（加法原理），得
c[i][j]=c[i−1][j−1]+c[i−1][j]
打家劫舍：中等
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
class Solution:
def rob(self, nums: List[int]) -> int:
cur, pre = 0, 0
for num in nums:
cur, pre = max(pre + num, cur), cur
return cur
解题思路：
典型的动态规划，以下按照标准流程解题。
- 状态定义：
设动态规划列表 dp ，dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额。
转移方程：
- 设： 有 n 个房子，前 n 间能偷窃到的最高金额是 dp[n] ，前 n−1 间能偷窃到的最高金额是 dp[n−1] ，此时向这些房子后加一间房，此房间价值为 num ；
- 加一间房间后： 由于不能抢相邻的房子，意味着抢第 n+1 间就不能抢第 n 间；那么前 n+1 间房能偷取到的最高金额 dp[n+1] 一定是以下两种情况的 较大值
- 不抢第 n+1 个房间，因此等于前 n 个房子的最高金额，即 dp[n+1]=dp[n] ；
- 抢第 n+1 个房间，此时不能抢第 n 个房间；因此等于前 n−1 个房子的最高金额加上当前房间价值，即 dp[n+1]=dp[n−1]+num ；
- 细心的我们发现： 难道在前 n 间的最高金额 dp[n] 情况下，第 n 间一定被偷了吗？假设没有被偷，那 n+1 间的最大值应该也可能是 dp[n+1]=dp[n]+num 吧？其实这种假设的情况可以被省略，这是因为：
- 假设第 n 间没有被偷，那么此时 dp[n]=dp[n−1] ，此时 dp[n+1]=dp[n]+num=dp[n−1]+num ，即两种情况可以 合并为一种情况 考虑；
- 假设第 n 间被偷，那么此时 dp[n+1]=dp[n]+num 不可取 ，因为偷了第 n 间就不能偷第 n+1 间。
- 最终的转移方程： dp[n+1]=max(dp[n],dp[n−1]+num)
·初始状态：
前 0 间房子的最大偷窃价值为 0 ，即 dp[0]=0 。
·返回值：
返回 dp 列表最后一个元素值，即所有房间的最大偷窃价值。
·简化空间复杂度：
我们发现 dp[n] 只与 dp[n−1] 和 dp[n−2] 有关系，因此我们可以设两个变量 cur和 pre 交替记录，将空间复杂度降到 O(1) 。
复杂度分析：
- 时间复杂度 O(N) ： 遍历 nums 需要线性时间；
- 空间复杂度 O(1) ： cur和 pre 使用常数大小的额外空间。
完全平方数：中等
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
一、记忆化搜索
把 1,4,9,16,⋯ 这些完全平方数视作物品体积，物品价值都是 1。由于每个数（物品）选的次数没有限制，所以本题是一道标准的完全背包问题。
按照视频中的做法，定义 dfs(i,j) 表示从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j，最少要选的数字个数。
<