二刷 LeetCode：118. 杨辉三角 198. 打家劫舍 复盘笔记

目录一、118. 杨辉三角题目回顾思路复盘代码实现Java易错点 二刷心得二、198. 打家劫舍题目回顾思路复盘基础 DP 实现Java空间优化版O (1) 空间易错点 二刷心得三、两道题的共性总结 二刷收获这两道题分别是动态规划入门和经典一维 DP的代表也是面试高频考点。二刷时我们重点拆解思路、优化写法顺便把易错点和通用模板总结清楚。一、118. 杨辉三角题目回顾给定一个非负整数numRows生成「杨辉三角」的前numRows行。在「杨辉三角」中每个数是它左上方和右上方的数的和。思路复盘杨辉三角的核心规律第i行从 0 开始有i1个元素每行的第一个和最后一个元素都是1中间元素triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]代码实现Javajava运行public ListListInteger generate(int numRows) { ListListInteger result new ArrayList(); for (int i 0; i numRows; i) { ListInteger row new ArrayList(); // 每行首尾为1 for (int j 0; j i; j) { if (j 0 || j i) { row.add(1); } else { // 中间元素 上一行的两个元素之和 row.add(result.get(i-1).get(j-1) result.get(i-1).get(j)); } } result.add(row); } return result; }易错点 二刷心得索引处理注意行号从 0 开始第i行的长度是i1避免越界。边界元素每行首尾元素必须单独处理为 1否则会出现i-1或j-1为负的越界错误。空间优化如果题目只要求返回第k行可以用一维数组滚动更新空间复杂度从 O (n²) 降到 O (n)。二、198. 打家劫舍题目回顾你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。思路复盘这是一维动态规划的经典题核心是定义状态和状态转移方程。状态定义dp[i]表示前i间房屋能偷窃到的最高金额。状态转移对于第i间房屋有两种选择偷第i间那么不能偷第i-1间最高金额为dp[i-2] nums[i]不偷第i间最高金额为dp[i-1]状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])初始状态dp[0] nums[0]只有一间房偷它dp[1] max(nums[0], nums[1])两间房偷金额大的结果dp[n-1]n 为房屋数量基础 DP 实现Javajava运行public int rob(int[] nums) { if (nums null || nums.length 0) return 0; if (nums.length 1) return nums[0]; int n nums.length; int[] dp new int[n]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] Math.max(dp[i-1], dp[i-2] nums[i]); } return dp[n-1]; }空间优化版O (1) 空间因为dp[i]只依赖dp[i-1]和dp[i-2]所以可以用两个变量滚动更新空间复杂度从 O (n) 降到 O (1)java运行public int rob(int[] nums) { if (nums null || nums.length 0) return 0; if (nums.length 1) return nums[0]; int prevPrev nums[0]; int prev Math.max(nums[0], nums[1]); for (int i 2; i nums.length; i) { int current Math.max(prev, prevPrev nums[i]); prevPrev prev; prev current; } return prev; }易错点 二刷心得边界处理数组长度为 0 或 1 时要单独判断避免索引越界。状态转移的理解dp[i]表示前i间的最高金额不是偷第i间的最高金额所以不偷第i间时dp[i] dp[i-1]。空间优化技巧一维 DP 中如果当前状态只依赖前两个状态就可以用变量代替数组大幅降低空间复杂度。三、两道题的共性总结 二刷收获动态规划的入门模板杨辉三角二维 DP 的基础从简单的递推关系入手理解 “上一行推导下一行” 的思路。打家劫舍一维 DP 的经典学会定义状态、找到转移方程理解 “选 / 不选” 两种决策的逻辑。优化意识从二维数组到一维数组再到变量滚动更新体会空间优化的思路。二刷时不仅要写出正确的代码还要思考如何优化时间和空间复杂度。面试重点杨辉三角重点是边界处理和递推关系常作为 DP 入门题考察。打家劫舍重点是状态转移方程和空间优化后续的环形打家劫舍、打家劫舍 III 都是它的变形题。