LeetCode 77组合——简单笔记1. 题目从1 ~ n中选择k个数字返回所有可能的组合。例如n 4, k 2 [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]2. 核心思想回溯把它理解成选择 → 递归 → 撤销选择 → 换下一个3. 两个重要变量path[]# 当前选择了哪些数字res[]# 保存所有答案4. 终止条件如果已经选够k个iflen(path)k:res.append(path[:])return这里path[:]是复制当前path。5. 回溯三板斧 ⭐path.append(i)# ① 选择 ibacktrack(i1)# ② 继续选择path.pop()# ③ 撤销选择这是这道题最重要的代码。6. 为什么是i 1因为组合不考虑顺序。已经选择1后只能选择2、3、4不能再选择1。这样可以避免[1,2] [2,1]这种重复。7. 完整代码classSolution:defcombine(self,n:int,k:int)-List[List[int]]:res[]path[]defbacktrack(start):iflen(path)k:res.append(path[:])returnforiinrange(start,n1):path.append(i)backtrack(i1)path.pop()backtrack(1)returnres⭐ 一句话记忆组合问题 从前往后选选够就保存选完以后撤销再换下一个。看到“从 n 个东西中选择 k 个并且要求所有可能情况” → 第一反应回溯。可以就按照你这个版本来记。这个版本其实更直观dp[i]和nums[i]下标完全对应很适合你现在学习。LeetCode 198 打家劫舍——简单笔记1. 核心思想每间房子只有两种选择不偷当前房子→dp[i-1]偷当前房子→ 不能偷前一间所以是dp[i-2] nums[i]因此dp[i]max(dp[i-1],dp[i-2]nums[i])2.dp[i]的含义 ⭐dp[i]表示偷到第 i 间房子时前 i1 间房子能够偷到的最大金额。例如nums [2, 7, 9, 3, 1] dp [2, 7, 11, 11, 12]3. 初始化只有一间房子dp[0]nums[0]只有前两间房子dp[1]max(nums[0],nums[1])因为两间相邻房子不能同时偷。4. 遍历从第三间房子开始foriinrange(2,n):dp[i]max(dp[i-1],dp[i-2]nums[i])5. 完整代码classSolution:defrob(self,nums:List[int])-int:nlen(nums)ifn1:returnnums[0]dp[0]*n dp[0]nums[0]dp[1]max(nums[0],nums[1])foriinrange(2,n):dp[i]max(dp[i-1],dp[i-2]nums[i])returndp[n-1]⭐ 一句话记忆当前房子偷不偷不偷dp[i-1]偷dp[i-2] nums[i]取两者最大值。这就是这道题最核心的 DP 思想。213. 打家劫舍 II —— 题目笔记一、题目核心房子围成一个环不能偷相邻的房子。特殊之处第 1 间和最后 1 间也是相邻的。所以第 1 间和最后 1 间不能同时偷。二、核心思路把环拆成两个普通问题因为第一间和最后一间不能同时偷所以只有两种情况情况 1不偷第一间考虑nums[1:n]例如[1, 2, 3, 1]变成[2, 3, 1]然后按照198. 打家劫舍的方法解决。情况 2不偷最后一间考虑nums[0:n-1]例如[1, 2, 3, 1]变成[1, 2, 3]同样按照普通打家劫舍解决。最后returnmax(a,b)三、普通打家劫舍的 DP我们在littlerob()中使用 198 的方法。dp[i]是什么dp[i]表示考虑前i1间房子能够偷到的最大金额。状态转移对于第i间房子有两种选择① 不偷第 i 间那么dp[i]dp[i-1]② 偷第 i 间因为相邻的不能偷所以第i-1间不能偷dp[i]dp[i-2]nums[i]因此dp[i]max(dp[i-1],dp[i-2]nums[i])四、初始化dp[0]nums[0]只有第一间房子只能偷第一间所以最大金额就是nums[0]第二间dp[1]max(nums[0],nums[1])因为第一间和第二间不能同时偷所以只能选择其中金额较大的。五、你的最终代码classSolution:defrob(self,nums:List[int])-int:# 只有一间房子直接返回iflen(nums)1:returnnums[0]# 解决普通的“打家劫舍”deflittlerob(nums:List[int])-int:nlen(nums)ifn1:returnnums[0]dp[0]*n dp[0]nums[0]dp[1]max(nums[0],nums[1])foriinrange(2,n):dp[i]max(dp[i-1],dp[i-2]nums[i])returndp[n-1]nlen(nums)# 情况1不偷第一间alittlerob(nums[1:n])# 情况2不偷最后一间blittlerob(nums[0:n-1])returnmax(a,b)六、为什么一定要判断len(nums)1这是这道题的一个特殊情况。例如nums[5]如果不提前返回nums[1:n]会变成[]nums[0:n-1]也会变成[]然后littlerob([])中dp[0]nums[0]就会报错。所以iflen(nums)1:returnnums[0]必须放在外层。七、这道题最重要的知识点① 环形问题 → 拆成两个线性问题记住不偷第一间 ↓ nums[1:] 不偷最后一间 ↓ nums[:-1] 最后取 max② DP 状态dp[i]表示偷前i1间房子能够得到的最大金额。③ 状态转移dp[i]max(dp[i-1],dp[i-2]nums[i])记忆偷当前 → 不能偷前一个不偷当前 → 继承前面的最大值④ 这道题和 198 的关系213 本质上就是 198 一个环形限制。198一排房子 ↓ 直接 DP213一圈房子 ↓ 不偷第一间 / 不偷最后一间 ↓ 分别做 198 ↓ 取最大值⭐ 一句话记忆打家劫舍 II 把环拆开成两排再分别使用打家劫舍 I 的 DP。1143. 最长公共子序列 —— 笔记1. 题目给两个字符串text1和text2找出它们最长公共子序列的长度。注意子序列可以删除字符但不能改变原来的顺序。例如text1 abcdeace是子序列但aec不是。2. 核心思路二维 DP定义dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。所以最终答案是dp[m][n]其中mlen(text1)nlen(text2)3. 为什么是二维因为我们同时考虑两个字符串text1 → i text2 → j所以需要dp[i][j]而不是像打家劫舍那样只需要一个下标。4. 状态转移情况一当前两个字符相同iftext1[i-1]text2[j-1]:dp[i][j]dp[i-1][j-1]1意思两个字符一样可以把这个字符加入公共子序列。所以左上角 1即dp[i-1][j-1] 1情况二当前两个字符不相同else:dp[i][j]max(dp[i-1][j],dp[i][j-1])因为当前两个字符不能同时作为匹配字符。所以有两种选择舍弃 text1 当前字符 → dp[i-1][j] 舍弃 text2 当前字符 → dp[i][j-1]取两者最大值。5. 初始化创建dp[[0]*(n1)for_inrange(m1)]为什么要1因为需要表示空字符串如果其中一个字符串长度为 0最长公共子序列 0所以dp[0][j] 0 dp[i][0] 0Python 中直接初始化成 0 即可。6. 为什么代码里是i-1这是这道题最容易混淆的地方。dp[i][j]表示的是前i个字符但是字符串下标从0开始。所以第i个字符对应text1[i-1]例如text1 abcde i 1 → text1[0] → a i 2 → text1[1] → b i 3 → text1[2] → c所以代码写text1[i-1]text2[j-1]7. 完整代码classSolution:deflongestCommonSubsequence(self,text1:str,text2:str)-int:mlen(text1)nlen(text2)dp[[0]*(n1)for_inrange(m1)]foriinrange(1,m1):forjinrange(1,n1):iftext1[i-1]text2[j-1]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])returndp[m][n]8. 做题模板遇到这道题可以按照下面的顺序想① 两个字符串 ↓ ② 二维 DP ↓ ③ dp[i][j] 前 i 个和前 j 个的答案 ↓ ④ 当前字符相同 ↓ 是 → 左上角 1 ↓ 否 → 上面和左边取最大值 ↓ ⑤ dp[m][n]⭐ 最后只记住这三个东西DP 定义dp[i][j]前i个字符和前j个字符的最长公共子序列长度。相同dp[i][j]dp[i-1][j-1]1左上角 1不同dp[i][j]max(dp[i-1][j],dp[i][j-1])上面和左边取最大这道题是非常经典的二维 DP 入门题后面很多字符串 DP 都可以从这个思路继续延伸。