朴素算法Bare Algo

动态规划

状态转移、背包问题及复杂状态压缩。

算法题

(21)

第 1 阶段:先把线性动态规划打牢

先练爬楼梯、打家劫舍、杨辉三角和不同路径,建立“状态怎么定义、转移从哪里来”的基本直觉。

70. 爬楼梯

简单
动态规划数学

198. 打家劫舍

中等
数组动态规划

118. 杨辉三角

简单
数组动态规划

62. 不同路径

中等
数学动态规划组合数学

152. 乘积最大子数组

中等
数组动态规划

第 2 阶段:掌握背包、拆分与序列型 DP

这一阶段开始处理零钱兑换、完全平方数、子集划分和最长递增子序列,重点是枚举顺序和一维二维状态设计。

322. 零钱兑换

中等
数组动态规划广度优先搜索

279. 完全平方数

中等
数学动态规划广度优先搜索

416. 分割等和子集

中等
数组动态规划

139. 单词拆分

中等
哈希表字符串动态规划字典树

300. 最长递增子序列

中等
数组二分查找动态规划

309. 买卖股票的最佳时机含冷冻期

中等
数组动态规划

337. 打家劫舍 III

中等
树深度优先搜索动态规划二叉树

647. 回文子串

中等
字符串动态规划

494. 目标和

中等
数组动态规划回溯

第 3 阶段:攻克网格与字符串进阶状态转移

最后进入最小路径和、最大正方形、最长公共子序列、编辑距离和最长有效括号,训练多维状态和复杂边界处理。

64. 最小路径和

中等
数组动态规划矩阵

221. 最大正方形

中等
数组动态规划矩阵

1143. 最长公共子序列

中等
字符串动态规划

72. 编辑距离

中等
字符串动态规划

32. 最长有效括号

困难
字符串动态规划栈

10. 正则表达式匹配

困难
字符串动态规划递归

96. 不同的二叉搜索树

中等
树动态规划二叉搜索树数学