一维动态规划示例

《职业生涯规划案例分析》- 分析成功职业规划案例 #生活知识# #生活指南# #职场建议# #职业规划书籍#

### LeetCode 198 打家劫舍 动态规划 Java 解法 #### 问题描述 给定一个非负整数数组 `nums`，表示每个位置上的房屋存放的金额。假设每间房之间有警报系统相连，如果两间相邻的房子在同一晚上被闯入，则会触发警报。计算在不触动警报的情况下，能够偷窃到的最高金额。 --- #### 动态规划思路 该问题可以通过动态规划来解决。设状态 `dp[i]` 表示考虑前 `i` 个房子时所能获得的最大收益。对于每一个房子有两种选择： - **偷当前房子**：则无法偷前一间房子，最大收益为 `dp[i-2] + nums[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 是房子的数量。 --- #### 实现代码 以下是基于上述分析的 Java 实现： ```java public class HouseRobber { public static int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } // 初始化两个变量代替整个 dp 数组 int prev1 = 0; // dp[i-1] int prev2 = 0; // dp[i-2] for (int num : nums) { int current = Math.max(prev1, prev2 + num); // 当前最优解 prev2 = prev1; // 更新 dp[i-2] prev1 = current; // 更新 dp[i-1] } return prev1; // 返回最后一个房子的结果 } public static void main(String[] args) { int[] nums = {2, 7, 9, 3, 1}; System.out.println(rob(nums)); // 输出结果应为 12 } } ``` --- #### 复杂度分析 - **时间复杂度**: 遍历一次数组即可完成计算，故时间为 O(n)[^4]。 - **空间复杂度**: 使用了常量级额外空间（仅保存两个变量），故空间复杂度为 O(1)[^4]。 --- #### 测试案例 测试输入 `[2, 7, 9, 3, 1]` 的运行过程如下： | 房子编号 | 当前房间金额 | 不偷此房间的最大值 (`prev1`) | 偷此房间的最大值 (`prev2 + num`) | 最大值 (`current`) | |-----------|----------------|----------------------------------|-------------------------------------|--------------------| | 0 | 2 | 0 | 2 | 2 | | 1 | 7 | 2 | 7 | 7 | | 2 | 9 | 7 | 11 | 11 | | 3 | 3 | 11 | 10 | 11 | | 4 | 1 | 11 | 12 | 12 | 最终返回值为 12。 ---

网址：一维动态规划示例 https://www.yuejiaxmz.com/news/view/1440689

相关内容

一维动态规划精讲
二维动态规划空间优化
动态规划
动态规划：空间优化技巧以及接龙型动态规划
动态规划精讲
动态规划教程：初学者指南
动态规划之0
算法动态规划01背包问题
动态规划的应用
动态规划：理解、应用与生活启示,

随便看看