力扣刷题汇总

动态规划

1 . 最大子序和 (Maximum Subarray Sum)

Leetcode 53. 最大子数组和经典dp

问题描述：给定一个整数数组，求其中和最大的连续子数组的和。

状态定义：dp[i] 表示以第 i 个元素结尾的最大子序和。

2 . 最长公共子序列 (Longest Common Subsequence, LCS)

Leetcode 1143. 最长公共子序列经典DP

问题描述：给定两个序列，求它们的最长公共子序列的长度。子序列不要求连续，但顺序必须保持一致。

状态定义：dp[i][j] 表示前 i 个字符的第一个序列和前 j 个字符的第二个序列的最长公共子序列的长度。

3 . 打家劫舍 (House Robber)

Leetcode 198. 打家劫舍动态规划

Leetcode 213. 打家劫舍 II 动态规划

Leetcode 740. 删除并获得点数 DP

问题描述：一排房子，每个房子内有一定金额。相邻的两间房子不能同时抢劫，求可以抢劫的最大金额。

状态定义：dp[i] 表示抢劫前 i 个房子的最大金额。

4 . 斐波那契数列 (Fibonacci Sequence)

Leetcode 509. 斐波那契数递归 / 动态规划

Leetcode 1137. 第 N 个泰波那契数

问题描述：斐波那契数列是一个常见的递推序列，其定义为： F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) for n ≥2
状态定义：dp[i] 表示斐波那契数列的第 i 项。

5. 爬楼梯问题 (Climbing Stairs)

Leecode 70. 爬楼梯 DP/矩阵快速幂

Leetcode 746. 使用最小花费爬楼梯

问题描述：一个人每次可以爬 1 步或 2 步，问有多少种不同的方式爬到第 n 阶楼梯。

状态定义：dp[i] 表示爬到第 i 阶楼梯的不同方法数。

6. 从矩阵的左上角到右下角

Leetcode 64. 最小路径和动态规划+空间优化

Leetcode 62. 不同路径动态规划+空间优化

Leetcode 63. 不同路径 II 动态规划

问题描述：一个人从矩阵grid的左上角到右下角的路径总数 / 最小路径和

状态定义：dp[i][j] 表示到grid[i][j]的路径总数 / 最小路径和。

7. 硬币找零问题 (Coin Change Problem)

Leetcode 322. 零钱兑换动态规划

Leetcode 518. 零钱兑换 II 动态规划

问题描述：给定一定面额的硬币和一个金额，求最少需要多少硬币来组成该金额。可以使用每种硬币多次。

状态定义：dp[i] 表示组成金额 i 所需的最小硬币数。

8.矩阵

Leetcode 120. 三角形最小路径和动态规划

Leetcode 931. 下降路径最小和动态规划

Leetcode 221. 最大正方形动态规划

9.字符串

Leetcode 5. 最长回文子串经典动态规划

问题描述：求一个字符串中最长的回文子串（回文是指正读和反读都相同的字符串）。
状态定义：构造一个二维数组 dp，其中 dp[i][j] 表示子串 s[i…j] 是否是回文串。当 s[i] == s[j]，s[i…j] 是否为回文取决于去掉首尾字符后的子串 s[i+1…j-1] 是否为回文，即 dp[i][j] = dp[i+1][j-1]。

Leetcode 139. 单词拆分动态规划

问题描述：给定一个字符串 s 和一个单词字典 wordDict（包含若干不重复的单词），判断字符串 s 是否可以被拆分为一个或多个在字典中出现的单词的组合。
状态定义：定义一个布尔数组 dp，其中 dp[i] 表示字符串 s[0…i-1] 是否可以被拆分成字典中的单词。字符串 s 的前 i 个字符是否能被拆分的问题可以理解为：如果存在一个位置 j（0 ≤ j < i），使得dp[j] = true（s[0…j-1] 可被拆分），并且s[j…i-1] 是字典中的单词。

Leetocde516. 最长回文子序列动态规划

问题描述：给一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
状态定义：定义 dp[i][j] 表示字符串 s 中第 i 到第 j 个字符之间的最长回文子序列长度。若 s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2，若 s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1])

10. 编辑距离 (Edit Distance)

Leetcode 72. 编辑距离动态规划

问题描述：给定两个字符串，求将一个字符串转化为另一个字符串的最小操作次数。允许的操作有插入、删除和替换字符。

状态定义：dp[i][j] 表示将字符串 A[0…i-1] 转化为 B[0…j-1] 的最小操作次数。

11.背包问题 (Knapsack Problem)

Leetcode 279. 完全平方数动态规划完全背包问题

Leetcode 377. 组合总和 Ⅳ 动态规划

Leetcode 474. 一和零多重背包问题，动态规划

问题描述：给定一些物品，每个物品有一个重量和一个价值，以及一个背包的容量。问如何选择物品，使得在不超过背包容量的情况下，物品的总价值最大化。

类型：

0/1 背包：每个物品只能选择一次。
完全背包：每个物品可以选择多次。
多重背包：每个物品有一个数量限制。
状态定义：dp[i][w]表示前 i 个物品，且总重量不超过 w 的最大价值。

Leetcode 300. 最长递增子序列动态规划 / 贪心 + 二分查找

Leetcode 673. 最长递增子序列的个数动态规划 / 贪心 + 二分查找

Leetcode 2140. 解决智力问题动态规划

Leetcode 91. 解码方法动态规划

Leetcode 983. 最低票价动态规划