企业官网建设流程全解析

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(i+1)# ② 继续选择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,n+1):path.append(i)backtrack(i+1)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 间房子时，前 i+1 间房子能够偷到的最大金额。

例如：

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:n=len(nums)ifn==1: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]

表示：

考虑前i+1间房子，能够偷到的最大金额。

状态转移

对于第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:n=len(nums)ifn==1: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]n=len(nums)# 情况1：不偷第一间a=littlerob(nums[1:n])# 情况2：不偷最后一间b=littlerob(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]

表示：

偷前i+1间房子能够得到的最大金额。

③ 状态转移

dp[i]=max(dp[i-1],dp[i-2]+nums[i])

记忆：

偷当前 → 不能偷前一个

不偷当前 → 继承前面的最大值

④ 这道题和 198 的关系

213 本质上就是 198 + 一个环形限制。

198：

一排房子 ↓ 直接 DP

213：

一圈房子 ↓ 不偷第一间 / 不偷最后一间 ↓ 分别做 198 ↓ 取最大值

⭐ 一句话记忆

打家劫舍 II = 把环拆开成两排，再分别使用打家劫舍 I 的 DP。

1143. 最长公共子序列 —— 笔记

1. 题目

给两个字符串text1和text2，找出它们最长公共子序列的长度。

注意：

子序列可以删除字符，但不能改变原来的顺序。

例如：

text1 = "abcde"

"ace"是子序列，但"aec"不是。

2. 核心思路：二维 DP

定义：

dp[i][j]

表示：

text1的前i个字符和text2的前j个字符的最长公共子序列长度。

所以最终答案是：

dp[m][n]

其中：

m=len(text1)n=len(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]*(n+1)for_inrange(m+1)]

为什么要+1？

因为需要表示：

空字符串

如果其中一个字符串长度为 0：

最长公共子序列 = 0

所以：

dp[0][j] = 0 dp[i][0] = 0

Python 中直接初始化成 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:m=len(text1)n=len(text2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):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 都可以从这个思路继续延伸。