每日一题70. 爬楼梯题目总体思路代码知识点198. 打家劫舍题目总体思路代码知识点2026.7.1870. 爬楼梯题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2输出2解释有两种方法可以爬到楼顶。1 阶 1 阶2 阶示例 2输入n 3输出3解释有三种方法可以爬到楼顶。1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶提示1 n 45总体思路递推关系推导设 dp[i]爬到第 i 阶楼梯的总方法数到达第 i 阶只有两种路径从 i-1 阶爬 1 步上来方法数 dp[i-1]从 i-2 阶爬 2 步上来方法数 dp[i-2]转移方程dp[i]dp[i−1]dp[i−2]自上而下的带备忘录的递归直接递归会大量重复计算用 map 存已经算过的阶数结果避免重复递归时间复杂度 O (n) 空间复杂度O (n)。① 输入 n直接拆解 f(n)f(n-1)f(n-2)递归向下求解子问题② 引入 map 备忘录缓存已经计算过的台阶结果避免重复递归纯暴力递归会重复计算大量子问题指数超时③ 递归终止条件n 1 返回 1、n2 返回 2④ 每次计算出新结果存入 map下次同阶查询直接读取缓存自上而下的迭代时间复杂度O (n) 空间复杂度O (1)① 不使用递归从最小已知状态 f(1)1、f(2)2 开始正向推导② 观察递推式f(i) 仅依赖前两项 f(i-1)、f(i-2)不需要存储完整 dp 数组③ 只用两个变量滚动保存前两阶的方案数循环从 3 遍历到 n不断更新当前值④ 循环结束后保存 f(n) 的变量即为答案时间复杂度O (n)仅单层 for 循环从 3 遍历到 n循环执行 n-2 次线性时间。代码自上而下的带备忘录的递归// 1. 自上而下的带备忘录的递归//go语言味funcclimbStairs(nint)int{memo:make(map[int]int)vardfsfunc(kint)intdfsfunc(kint)int{ifk0{return1}ifk1{return1}ifk2{return2}ifmemo[k]!0{returnmemo[k]}memo[k]dfs(k-1)dfs(k-2)returnmemo[k]}returndfs(n)}//分开写funcclimbStairs(nint)int{memo:make(map[int]int)returndfs(n,memo)}funcdfs(kint,memomap[int]int)int{ifk0{return1}ifk1{return1}ifk2{return2}ifval,exist:memo[k];exist{returnval}res:dfs(k-1,memo)dfs(k-2,memo)memo[k]resreturnres}//详细注释packagemainimportfmt// climbStairs 主入口函数funcclimbStairs(nint)int{// memo备忘录key台阶数value对应方法总数缓存已计算结果memo:make(map[int]int)// 调用递归辅助函数returndfs(n,memo)}// dfs 递归函数计算爬到k阶的方法数funcdfs(kint,memomap[int]int)int{// 终止条件1k1只有1种走法ifk1{return1}// 终止条件2k2有2种走法ifk2{return2}// 先查备忘录如果已经计算过直接返回不用重复递归ifval,exist:memo[k];exist{returnval}// 未缓存递推计算 f(k) f(k-1)f(k-2)res:dfs(k-1,memo)dfs(k-2,memo)// 存入备忘录后续查询直接复用memo[k]resreturnres}funcmain(){fmt.Printf(n2方法数%d\n,climbStairs(2))// 输出2fmt.Printf(n3方法数%d\n,climbStairs(3))// 输出3fmt.Printf(n5方法数%d\n,climbStairs(5))// 输出8}自上而下的迭代funcclimbStairs(nint)int{ifn1{return1}ifn0{return1}ifn2{return2}prev2:1//注意这里前一个和前两个prev1:2fori:3;in;i{cur:prev1prev2 prev2prev1 prev1cur}returnprev1}// 详细注释packagemainimportfmt// climbStairs 迭代滚动变量实现funcclimbStairs(nint)int{// 边界判断ifn1{return1}ifn2{return2}// prev1dp[i-1] 前一阶的方法数// prev2dp[i-2] 前两阶的方法数prev2:1// dp[1]prev1:2// dp[2]// 从第3阶开始循环到第n阶fori:3;in;i{// 当前阶方法数 前一阶 前两阶cur:prev1prev2// 滚动更新往前移位prev2prev1 prev1cur}// 循环结束 prev1 就是dp[n]returnprev1}funcmain(){fmt.Println(climbStairs(2))// 2fmt.Println(climbStairs(3))// 3fmt.Println(climbStairs(10))// 89}知识点递归函数函数调用自身、终止条件设计、栈调用原理map 备忘录缓存map [int] int 存储已计算结果消除重复递归记忆化搜索迭代循环for 循环滚动变量自底向上递推切片 / 变量滚动优化舍弃完整 dp 数组O (1) 空间边界条件判断n1、n2 特殊值处理函数封装主逻辑 辅助递归函数分离198. 打家劫舍题目你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。示例 1输入[1,2,3,1]输出4解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。示例 2输入[2,7,9,3,1]输出12解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12 。提示1 nums.length 1000 nums[i] 400总体思路状态定义dp[i]偷窃前 i 间房屋能获得的最大金额dp[0] 0没有房屋时收益为 0dp[1] nums[0]只有 1 间房屋只能偷这一间状态转移方程dp[i]max(dp[i−1], dp[i−2]nums[i−1])不偷第i间房最大收益等于前i-1间的最优解dp[i-1]偷第i间房不能偷相邻的第i-1间收益等于前i-2间最优解 当前房屋金额nums[i-1]最终结果dp[nums.size()]偷完所有n间房屋的最大收益时间复杂度O(n)n 为房屋数量仅单层循环遍历一次数组每次循环做一次最大值计算空间复杂度O(n) 开辟了长度为 n1 的 dp 数组存储子问题结果代码funcrob(nums[]int)int{n:len(nums)dp:make(map[int]int,n1)ifn0{dp[1]nums[0]}fori:2;in;i{dp[i]max(dp[i-1],dp[i-2]nums[i-1])}returndp[n]}//详细注释packagemainimportfmt// max 辅助函数返回两个整数的较大值替代C的std::maxfuncmax(a,bint)int{ifab{returna}returnb}// rob 主函数计算能偷窃的最大金额funcrob(nums[]int)int{// 获取房屋总数等价C nums.size()n:len(nums)// 创建dp切片长度n1初始值全为0等价vectorint dp(nums.size() 1, 0)dp:make([]int,n1)// 边界初始化如果存在房屋前1间房的最大收益就是nums[0]ifn0{dp[1]nums[0]}// 从第2间房遍历到第n间房等价C for (int i 2; i nums.size() 1; i)fori:2;in;i{// 状态转移两种选择取最大值// nums[i-1]是因为dp下标从1开始原nums下标从0开始存在偏移dp[i]max(dp[i-1],dp[i-2]nums[i-1])}// 返回所有房屋的最优解等价return dp[nums.size()]returndp[n]}funcmain(){// 测试用例1fmt.Println(rob([]int{1,2,3,1}))// 输出4// 测试用例2fmt.Println(rob([]int{2,7,9,3,1}))// 输出12}知识点算法知识点动态规划最优子结构全局最优解可以由子问题的最优解推导得到无后效性后续决策只依赖前面的最优结果不关心之前具体怎么选的下标偏移技巧dp 数组从 1 开始用dp[0]0统一空数组边界简化判断逻辑Go 语言知识点切片操作make([]int, length)创建指定长度、零值初始化的切片替代 C vector长度获取len(nums)获取切片元素个数for 循环语法Go 经典三段式循环实现和 C 一致的遍历逻辑自定义工具函数封装max实现两数比较边界条件处理用if n0处理输入为空切片的特殊情况