LeetCode刷题总结-动态规划篇

LeetCode刷题总结-动态规划篇 

本文总结LeetCode上有动态规划的算法题，推荐刷题总数为54道。具体考点分析如下图：

1.中心扩展法

题号：132. 分割回文串 II，难度困难

2.背包问题

题号：140. 单词拆分 II，难度困难（最佳解法采用记忆化回溯）

题号：416. 分割等和子集，难度中等

题号：474. 一和零，难度中等

题号：638. 大礼包，难度中等（回溯法解决，分解为子问题，有动态规划的思路）

3.最短路径问题

矩阵空间，逆向动态规划

题号：174. 地下城游戏，难度困难

题号：312. 戳气球，难度困难，自底向上

4.结合贪心的思想

题号：188. 买卖股票的最佳时机 IV，难度困难

题号：321. 拼接最大数，难度困难

5.矩阵类型问题（区域检索问题）

题号：221. 最大正方形，难度中等

题号：304. 二维区域和检索 - 矩阵不可变，难度中等

题号：363. 矩形区域不超过 K 的最大数值和，难度困难

题号：576. 出界的路径数，难度中等（不同行走路径问题）

6.数学问题

题号：264. 丑数 II，难度中等（三指针法）

题号：600. 不含连续1的非负整数，难度困难（斐波那契数列问题）

题号：650. 只有两个键的键盘，难度中等

题号：808. 分汤，难度中等

题号：837. 新21点，难度中等

题号：1039. 多边形三角剖分的最低得分，难度中等

元素对问题：

题号：629. K个逆序对数组，难度困难

题号：646. 最长数对链，难度中等

题号：1024. 视频拼接，难度中等

题号：1105. 填充书架，难度中等

7.子序列或者子集问题

题号：300. 最长上升子序列，难度中等（二分查找）

题号：368. 最大整除子集，难度中等

题号：392. 判断子序列，难度简单（大数据分析问题）

题号：516. 最长回文子序列，难度中等

题号：523. 连续的子数组和，难度中等

题号：673. 最长递增子序列的个数，难度中等

题号：813. 最大平均值和的分组，难度中等

题号：873. 最长的斐波那契子序列的长度，难度中等

题号：940. 不同的子序列 II，难度困难

题号：1155. 掷骰子的N种方法，难度中等

8.排序问题

题号：354. 俄罗斯套娃信封问题，难度困难

题号：903. DI 序列的有效排列，难度困难

9.博弈问题

题号：375. 猜数字大小 II，难度中等（极大极小化思想）

题号：464. 我能赢吗，难度中等

题号：486. 预测赢家，难度中等

题号：740. 删除与获得点数，难度中等

题号：801. 使序列递增的最小交换次数，难度中等

题号：877. 石子游戏，难度中等

10.实际场景应用问题

题号：403. 青蛙过河，难度困难（数组形式的问题）

题号：517. 超级洗衣机，难度困难

题号:  546. 移除盒子，难度困难

题号：664. 奇怪的打印机，难度困难

题号：790. 多米诺和托米诺平铺，难度中等

题号：983. 最低票价，难度中等

11.回环问题

题号：467. 环绕字符串中唯一的子字符串，难度中等

12.表达式求值问题

题号：494. 目标和，难度中等（01背包问题）

题号：964. 表示数字的最少运算符，难度困难

13.字符串问题

题号：712. 两个字符串的最小ASCII删除和，难度中等

题号：943. 最短超级串，难度困难

题号：1092. 最短公共超序列，难度困难

14.图论问题

题号：847. 访问所有节点的最短路径，难度困难