动态规划解题套路框架

学习计划：

最长回文子序列

〇、必读文章

1、数据结构和算法学习指南（学习算法和刷题的框架思维）

• 了解数据结构的操作和遍历（迭代or递归）
• 从树刷起，结合框架思维，有利于理解（回溯、动态规划、分治等）

2、动态规划详解（动态规划解题套路框架）

• 过程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法
• 特征：重叠子问题-->使用备忘录&自底向上，最优子结构，状态转移方程
• 例题：凑零钱（dp[i] = min(dp[i], 1 + dp[i - coin])）

3、回溯算法详解（修订版）=DFS-----做选择

• 3个问题：参数记录路径、选择列表（做选择和撤销选择）、结束条件

result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:  
    做选择  
    backtrack(路径, 选择列表)  
    撤销选择

• 例题：八皇后问题、全排列问题

4、BFS 算法框架套路详解------求最短距离

• 与DFS对比：使用队列，路径短，空间复杂度高
• 问题本质：在图中找起点到终点的最近距离，队列入队访问邻接，记录访问过的
• 例题：二叉树的最小高度（齐头并进，BFS时间复杂度低）、打开密码锁的最少次数（可以使用双向BFS，无需掌握）
• 步骤：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue q; // 核心数据结构
Set visited; // 避免走回头路

q.offer(start); // 将起点加入队列  
visited.add(start);  
int step = 0; // 记录扩散的步数

while (q not empty) {  
    int sz = q.size();  
    /\* 将当前队列中的所有节点向四周扩散 \*/  
    for (int i = 0; i < sz; i++) {  
        Node cur = q.poll();  
        /\* 划重点：这里判断是否到达终点 \*/  
        if (cur is target)  
            return step;  
        /\* 将 cur 的相邻节点加入队列 \*/  
        for (Node x : cur.adj())  
            if (x not in visited) {  
                q.offer(x);  
                visited.add(x);  
            }  
    }  
    /\* 划重点：更新步数在这里 \*/  
    step++;  
}  

}

5、我作了首诗，保你闭着眼睛也能写对二分查找

• 防止两数相加产生溢出：mid = left + (right - left) / 2;
• while里面是小于等于
• 寻找左侧边界的二分：相等时不直接返回

int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}

• 寻找右侧边界：left = mid + 1;「搜索区间」全都统一成两端都闭

6、我写了套框架，把滑动窗口算法变成了默写题

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        …

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            …
        }
    }
}

• 例题：最小覆盖子串、字符串排列、找所有字母的异位词、最长无重复子串
• 引出双指针问题：
  • 快慢指针（链表，有环）
  • 左右指针（数组或字符串问题，如二分，有序数组两数之和等于目标数，反转数组）

7、团灭 LeetCode 股票买卖问题

• 通用解法：穷举，循环内部分别使用min和max；多次买卖用贪心/递归；限定交易次数递归参数传k递减；冷冻期改变递归函数dp的参数；手续费改变比较max的值
• （状态机）多维DP数组的状态转移方程：针对几种股票类型分别使用db table解决，其中限定次数的使用三维dp表

8、经典动态规划：打家劫舍系列问题

• 例题：标准动规、环形数组、二叉树打劫（相连的房子不能被打劫）

int res = Math.max(
// 不抢，去下家
dp(nums, start + 1),
// 抢，去下下家
nums[start] + dp(nums, start + 2)
);

• 自顶向下：递归调用dp函数，自底向上：定义dp数组
• 二叉树：抢孩子的左和右孩子

Map memo = new HashMap<>();
public int rob(TreeNode root) {
if (root == null) return 0;
// 利用备忘录消除重叠子问题
if (memo.containsKey(root))
return memo.get(root);
// 抢，然后去下下家
int do_it = root.val
+ (root.left == null ?
0 : rob(root.left.left) + rob(root.left.right))
+ (root.right == null ?
0 : rob(root.right.left) + rob(root.right.right));
// 不抢，然后去下家
int not_do = rob(root.left) + rob(root.right);

int res = Math.max(do\_it, not\_do);  
memo.put(root, res);  
return res;  

}

9、一个方法解决三道区间问题

• 区间问题：即线段问题，包括合并线段，找线段的交集；技巧：排序&画图
• 区间覆盖问题：例删除被覆盖的区间--排序后分3种情况，相交区间合并，不相交则更新起点终点
• 区间合并问题：排序，根据条件进行合并
• 区间交集问题：讨论两个交集的各种情况，并根据大小决定更新哪个list的下标

10、一个函数秒杀 2Sum 3Sum 4Sum 问题

• 两数之和：排序+双指针；去重数对：相等时指针相加
• 三数之和：第一个数不重复&调用两数之和的方法
• 四数之和：第一个数不重复&调用三数之和的方法
• ……：编写递归函数，参数传递n表示几数之和

11、手把手带你刷二叉树（第一期）

• 翻转二叉树：前序
• （完美二叉树）填充二叉树节点的右侧指针：传递两个参数，前序node1.next = node2;
• 二叉树展开为链表：没看懂

12、经典动态规划：0-1 背包问题

• 状态和选择、dp数组的定义

dp[i][w] = max( 把物品i装进背包, 不把物品i装进背包 )　

• 状态转移方程

dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1] )

• 代码

int knapsack(int W, int N, vector& wt, vector& val) {
// vector 全填入 0，base case 已初始化
vector> dp(N + 1, vector(W + 1, 0));
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i-1] < 0) {
// 当前背包容量装不下，只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包，择优
dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],
dp[i - 1][w]);
}
}
}

return dp\[N\]\[W\];  

}

13、我用四个命令概括了 Git 的所有套路

• 三个分区：working directory工作目录，stage/index area暂存区，commit history提交历史。
• git status查看前两个分区，git log查看提交日志的内容
• git checkout .：将工作目录修改过的文件恢复为暂存区的文件，不会删除在工作目录创建的新文件
• git commit --amend：修改合并，不会新创建一个commit到history中
• git reset X：对X文件的修改，不会提交到history中/把对a.txt的修改从stage区撤销，但依然保存在work dir中，变为unstage的状态。

14、提高刷题幸福感的小技巧

• 递归函数debug时，在递归函数前后分别打印关键变量的值。