• 代码随想录算法训练营 动态规划part08

    一、打家劫舍 

    198. 打家劫舍 - 力扣（LeetCode）

    • 设动态规划列表 dp，dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额。
    • 设： 有 n 个房子，前 n 间能偷窃到的最高金额是 dp[n]，前 n−1 间能偷窃到的最高金额是 dp[n−1] ，此时向这些房子后加一间房，此房间价值为 num ；
    • 加一间房间后： 由于不能抢相邻的房子，意味着抢第 n+1 间就不能抢第 n 间；那么前 n+1 间房能偷取到的最高金额 dp[n+1]一定是以下两种情况的 较大值 ：                                                        1.不抢第 n+1 个房间，因此等于前 n 个房子的最高金额，即dp[n+1]=dp[n] ；                           2.抢第 n+1 个房间，此时不能抢第 n 个房间；因此等于前 n−1 个房子的最高金额加上当前房间价值，即 dp[n+1]=dp[n−1]+num ；
    • 最终的转移方程： dp[n+1]=max(dp[n],dp[n−1]+num)
    • 初始状态：前 0 间房子的最大偷窃价值为 0 ，即 dp[0]=0 。
    • 返回值：返回 dp 列表最后一个元素值，即所有房间的最大偷窃价值。
    1. class Solution {
    2.     public int rob(int[] nums) {
    3.         int pre = 0, cur = 0, tmp;
    4.         for(int num : nums) {
    5.             tmp = cur;
    6.             cur = Math.max(pre + num, cur);
    7.             pre = tmp;
    8.         }
    9.         return cur;
    10.     }
    11. }
    12.

    二、打家劫舍II  

    213. 打家劫舍 II - 力扣（LeetCode）

    1. class Solution {
    2.     public int rob(int[] nums) {
    3.         if(nums.length == 0) return 0;
    4.         if(nums.length == 1) return nums[0];
    5.         return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), 
    6.                         myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    7.     }
    8.     private int myRob(int[] nums) {
    9.         int pre = 0, cur = 0, tmp;
    10.         for(int num : nums) {
    11.             tmp = cur;
    12.             cur = Math.max(pre + num, cur);
    13.             pre = tmp;
    14.         }
    15.         return cur;
    16.     }
    17. }
    18.

    三、打家劫舍III

    337. 打家劫舍 III - 力扣（LeetCode）

    1. class Solution {
    2.     public int rob(TreeNode root) {
    3.         int[] rootStatus = dfs(root);
    4.         return Math.max(rootStatus[0], rootStatus[1]);
    5.     }
    6.  
    7.     public int[] dfs(TreeNode node) {
    8.         if (node == null) {
    9.             return new int[]{0, 0};
    10.         }
    11.         int[] l = dfs(node.left);
    12.         int[] r = dfs(node.right);
    13.         int selected = node.val + l[1] + r[1];
    14.         int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
    15.         return new int[]{selected, notSelected};
    16.     }
    17. }

  • 相关阅读:
    ubuntu18.04安装mysql5.7并配置数据存储路径
    【嵌入式Linux】5.Ubuntu 交叉编译工具链安装
    Spring启动源码分析以及生命周期
    Mybatis-Plus入门（新版3.5.2）
    免杀对抗-宏免杀
    快捷键专栏 IDEA、Navicat、电脑、Excle、Word等
    应用架构和实践
    [oeasy]python0010_hello_world_unix_c历史迷因
    基于QWebEngine实现无头浏览器
    Spring Bean自动装配
  • 原文地址：https://blog.csdn.net/m0_63297917/article/details/133178498