70. 爬楼梯
难度 简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
官方
思路：动态规划 f(x)=f(x−1)+f(x−2) f(0)=1 f(1)=1 感觉就像斐波那契数列 用了滚动数组
class Solution { public int climbStairs(int n) { int p = 0, q = 0, r = 1; for (int i = 1; i <= n; ++i) { p = q; q = r; r = p + q; } return r; } }
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 <= 100
- 0 <= nums[i] <= 400
官方
思路： 最简单子问题 只有1件，只能偷这间 只有2件，偷金额大的那间 k>2时 偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。 在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[length - 1]; } }
上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。
class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int first = nums[0], second = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; } }
复杂度分析
- 时间复杂度：O(n)O(n)，其中 nn 是数组长度。只需要对数组遍历一次。
- 空间复杂度：O(1)O(1)。使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)O(1)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
120. 三角形最小路径和
难度 中等
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]] 输出：-10
提示：
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -104 <= triangle[i][j] <= 104
进阶：
你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
题解
思路：贪心算法 感觉可以用贪心算法 每次都走最小，总数就是最小
class Solution { public int minimumTotal(List<List<Integer>> triangle) { int min=0; int m=0; int indexM=0; for(int i=0;i<triangle.size();i++){ List<Integer> l=triangle.get(i); if(i==0){ indexM=0; m=l.get(0); }else{ if(l.get(indexM)<l.get(indexM+1)){ m=l.get(indexM); indexM=indexM; }else{ m=l.get(indexM+1); indexM=indexM+1; } } min+=m; } return min; } }
贪心不一定是最小的，只是相对最优的解法
官方
class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[][] f = new int[n][n]; f[0][0] = triangle.get(0).get(0); for (int i = 1; i < n; ++i) { f[i][0] = f[i - 1][0] + triangle.get(i).get(0); for (int j = 1; j < i; ++j) { f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j); } f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i); } int minTotal = f[n - 1][0]; for (int i = 1; i < n; ++i) { minTotal = Math.min(minTotal, f[n - 1][i]); } return minTotal; } }
