LeetCode 解题思路 42（Hot 100）

解题思路：

1. dp 数组的含义： 考虑下标 i，能偷的最大金额 dp[i]。
2. 递推公式： dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。
3. dp 数组初始化： dp[0] = nums[0]，dp[1] = Math.max(nums[0], nums[1])。
4. 遍历顺序： 从 i = 2 开始，直到 i = nums.length - 1。
5. 打印 dp 数组

Java代码：

class Solution {public int rob(int[] nums) {if (nums.length == 1) return nums[0];if (nums.length == 2) return Math.max(nums[0], nums[1]);int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++)dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);return dp[nums.length - 1];}
}

复杂度分析：

• 时间复杂度： O(n)，其中 n 是房屋数量。只需遍历一次数组。
• 空间复杂度： O(1)，仅使用常数级别的额外空间。
  

解题思路：

1. dp 数组的含义： 装满容量为 i 的背包，最少的物品个数为 dp[i]
2. 递推公式： dp[i] = Math.min(dp[i], dp[i - coin] + 1)。
3. dp 数组初始化： dp[0] = 0，dp[i] = amount + 1。
4. 遍历顺序： 与排列组合无关，从 i = 1 开始，直到 i = amount。
5. 打印 dp 数组

Java代码：

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int coin : coins) {if (i >= coin) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}

复杂度分析：

• 时间复杂度： O(amount × coins.length)，遍历所有金额和硬币组合。
• 空间复杂度： O(amount)，仅需一维数组存储状态。