算法训练营 - 学习笔记 - 第六周

接上周的动态规划。

DP 模板

1. 找重复子问题

2. 定义状态数组

3. 定义 DP 方程

不能靠经验，人肉递归去解决问题，要转换成计算机的思维。要找到自相似、重复性、把它化繁为简，同时逻辑上能够去证明。

动态规划（二）

爬楼梯问题

DP 方程：F(n) = F(n-1) + F(n-2)

爬楼梯变形：

1. 1, 2, 3

2. 相邻两步的步伐不能相同

实战题目解析：三角形最小路径和

1. brute-force: 递归，n 层：left or right, 2^n

2. DP

3. 重复性（分治）problem(i, j) = min(sub(i+1, j), sub(i+1, j+1) + a[i][j])

4. 定义状态数组 f[i,j]

5. DP 方程 f[i, j] = min(f[i+1, j], f[i+1, j+1]) + a[i, j]

实战题目解析：最大子序列和

最大子序列和 vs 最大子序列集

给定一个整数数组 nums, 找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

1. 暴力：O(n^2)，枚举子数组开始和结尾。

2. DP

3. 分治（子问题） max_sum(i) = Max(max_sum(i-1), 0) + a[i]

4. 转换数组定义 f[i]

5. DP 方程 f[i] = Max(f[i-1], 0) + a[i]

Coin Change

1. 递归

2. BFS

3. DP

4. subproblem

5. DP array f(n) = min{f(n-k)}, for k in [1, 2, 5]}) +1

6. DP 方程

实战题目解析：打家劫舍(house robber)

不能同时偷两个相邻的房间，使得偷窃的金额最高。

1. a[i][0, 1], 0...i 能偷到的 max value

2. 0: 不偷， 1：偷

3. DP 方程

4. a[i][0] = max(a[i-1][0], a[i-1][1])

5. a[i][1] = a[i-1][0] + nums[i]

def rob(self, nums):  pre = 0  now = 0  for i in nums:    pre, now = now, max(pre + i, now)