力扣刷题汇总
动态规划
1 . 最大子序和 (Maximum Subarray Sum)
问题描述：给定一个整数数组，求其中和最大的连续子数组的和。
状态定义：dp[i] 表示以第 i 个元素结尾的最大子序和。
2 . 最长公共子序列 (Longest Common Subsequence, LCS)
问题描述：给定两个序列，求它们的最长公共子序列的长度。子序列不要求连续，但顺序必须保持一致。
状态定义：dp[i][j] 表示前 i 个字符的第一个序列和前 j 个字符的第二个序列的最长公共子序列的长度。
3 . 打家劫舍 (House Robber)
问题描述：一排房子，每个房子内有一定金额。相邻的两间房子不能同时抢劫，求可以抢劫的最大金额。
状态定义：dp[i] 表示抢劫前 i 个房子的最大金额。
4 . 斐波那契数列 (Fibonacci Sequence)
问题描述：斐波那契数列是一个常见的递推序列，其定义为： F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) for n ≥2
状态定义：dp[i] 表示斐波那契数列的第 i 项。
5. 爬楼梯问题 (Climbing Stairs)
问题描述：一个人每次可以爬 1 步或 2 步，问有多少种不同的方式爬到第 n 阶楼梯。
状态定义：dp[i] 表示爬到第 i 阶楼梯的不同方法数。
6. 从矩阵的左上角到右下角
问题描述：一个人从矩阵grid的左上角到右下角的路径总数 / 最小路径和
状态定义：dp[i][j] 表示到grid[i][j]的路径总数 / 最小路径和。
7. 硬币找零问题 (Coin Change Problem)
问题描述：给定一定面额的硬币和一个金额，求最少需要多少硬币来组成该金额。可以使用每种硬币多次。
状态定义：dp[i] 表示组成金额 i 所需的最小硬币数。
8.矩阵
9.字符串
问题描述：求一个字符串中最长的回文子串（回文是指正读和反读都相同的字符串）。
状态定义：构造一个二维数组 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]。
问题描述：给定一个字符串 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] 是字典中的单词。
问题描述：给一个字符串 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)
问题描述：给定两个字符串，求将一个字符串转化为另一个字符串的最小操作次数。允许的操作有插入、删除和替换字符。
状态定义：dp[i][j] 表示将字符串 A[0…i-1] 转化为 B[0…j-1] 的最小操作次数。
11.背包问题 (Knapsack Problem)
Leetcode 279. 完全平方数 动态规划 完全背包问题
问题描述：给定一些物品，每个物品有一个重量和一个价值，以及一个背包的容量。问如何选择物品，使得在不超过背包容量的情况下，物品的总价值最大化。
类型：
0/1 背包：每个物品只能选择一次。
完全背包：每个物品可以选择多次。
多重背包：每个物品有一个数量限制。
状态定义：dp[i][w]表示前 i 个物品，且总重量不超过 w 的最大价值。
Leetcode 300. 最长递增子序列 动态规划 / 贪心 + 二分查找
Leetcode 673. 最长递增子序列的个数 动态规划 / 贪心 + 二分查找
二分
Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置 二分
指针
树
Leetcode 144. 二叉树的前序遍历 递归/迭代/Morris遍历
leetcode 94. 二叉树的中序遍历 递归/迭代/Morris 遍历
Leetcode 104. 二叉树的最大深度 BFS / 递归
Leetcode 106. 从中序与后序遍历序列构造二叉树 递归
Leetcode 105. 从前序与中序遍历序列构造二叉树 递归
原文地址：https://blog.csdn.net/qq_45791939/article/details/144695711
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！