目录 爬楼梯 背包问题 热门题🔥 爬楼梯 一维爬楼梯 先从简单但最经典的开始！ 70. 爬楼梯：假设你正在爬一个 n 阶的楼梯，每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶呢？ 思路：定义 dp 表示爬 i+1 阶楼梯的方法总数。 状态转移方程：dp = dp + dp 。 初始值：dp[0] = 1，dp[1] = 2 。 空间优化：观察到一旦算出 dp ，dp[i−2] 及其左边的状态就永远不会用到了。 二维爬楼梯 62. 不同路径：从 m x n 网格的左上角开始，每次只能向下或者向右移动 1 步，到达网格的右下角共有多少条不同的路径？ 思路：定义 dpi 表示到达网格 (i, j) 的方法总数。 状态转移方程：dpi = dpi-1 + dpi 。 初始值：i = 0 或 j = 0 时，dpi = 0 。 类似问题： 118. 杨辉三角 119. 杨辉三角 II 背包问题 问题描述：给定容量 target，以及一组物品的大小数组 weights，如何选取物品使得正好填满容量？ 完全背包问题 每种物品可以无限次使用。 0/1背包问题 每种物品最多只能被选取一次。 例题： 416. 分隔等和子集（0/1背包问题） 热门题🔥 32. 最长有效括号 问题描述：给定只包含 '(' 和 ')' 的字符串，找出最长有效且连续括号子串的长度。 - 示例 1：输入："(()" 输出：2 - 示例 2：输入：")()())" 输出：4 - 示例 3：输入："()(())" 输出：6 思路：定义 dp 表示以下标 i 字符结尾的最长有效括号长度。以 '(' 结尾的子串对应的 dp 值必定为 0 ，因此我们只需讨论以 ')' 结尾的情况： s = ')' 且 s[i−1] = '('：此时字符串形如 "……()" 。因此 i > 1 时，有 dp = dp[i−2] + 2 ；如果 i = 1 ，则 dp 直接等于 2 。 s = ')' 且 s[i−1] = ')'：此时字符串形如 "……))" 。因此去找 i 前面对应字符 prev 是否为 '(' ，其下标为 i 减去前一个字符已匹配的长度（i - dp - 1）；如果匹配，则 dp 在 dp 的基础上加 2 ；如果 prev 前还有字符，则再加上 prev 前已匹配的长度 dp - 2] 。 300. 最长递增子序列 问题描述：找出整数数组 nums 中最长严格递增子序列（可不连续但按序）的长度。 - 示例 1：输入：[0,1,0,3,2,3] 输出：4（即 [0,1,2,3]） - 示例 2：输入：[7,7,7,7,7,7,7] 输出：1 （即 [7]） 思路：定义 dp 表示以下标 i 的整数结尾的子序列最长长度。 状态转移方程：dp = max{dp} + 1，其中 0 < j < i, nums > nums ；若所有 nums 都大于 nums ，则 dp = 1。 初始值：dp[0] = 1 。