草庐IT

动态规划(17)、337. 打家劫舍III

arvinbrick 2023-03-28 原文

题目连接:337. 打家劫舍 III - 力扣(LeetCode)

 

 

题目分析:

  二叉树的后续遍历,dp[root] 表示 root节点的最大收益

        dp[root] = max(dp[root.left] + dp[root.right], root.val + dp[root.left.left] + dp[root.left.right] + dp[root.right.left] + dp[root.right.right])

我们可以在原始的二叉树上进行记录,因为题目中没有说不允许改变二叉树的内容;

我们使用二叉树的后续遍历,当前节点的最大收益为取当前节点,和不取当前节点的最大值,不取当前节点的话那就是两个子数的根节点

的值之和,如果取当前节点的话,由于不能相邻的节点一起偷,所以这时候其收益为当前节点的数值加上左节点的左右节点的数值和右节

点的左右节点数值之和(如果他们存在的话)

 

代码实现如下:

  

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        // 二叉树的后续遍历,dp[root] 表示 root节点的最大收益
        // dp[root] = max(dp[root.left] + dp[root.right], 
            // root.val + dp[root.left.left] + dp[root.left.right] + dp[root.right.left] + dp[root.right.right])

        dfs(root);

        return root.val;
    }


    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        dfs(root.left);
        dfs(root.right);

        root.val = Math.max(
            (root.left == null ? 0:root.left.val) + 
            (root.right == null? 0:root.right.val), 
            root.val + 
            (root.left == null? 0: (root.left.left == null ? 0: root.left.left.val)) +
            (root.left == null? 0: (root.left.right == null ? 0: root.left.right.val)) + 
            (root.right == null? 0: (root.right.left == null ? 0: root.right.left.val)) +
            (root.right == null? 0: (root.right.right == null ? 0: root.right.right.val)) 
        );

    }
}
 
复杂度分析:时间复杂度 O(n)
                     空间复杂度:O(n)
递归实现的本质也是系统帮我们建立了栈结构,而系统栈需要记住每个节点的值,所以空间复杂度仍为O(n)。

 

有关动态规划(17)、337. 打家劫舍III的更多相关文章

  1. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组?例如,假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在,对于用户输入的每一本书,我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  2. ruby - 是否可以将 IRB 提示配置为动态更改? - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录,但我不知道如何在每个命令后进行提示更新。最终,我想在日常工作中更多地使用IRB,让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  3. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先,我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  4. ruby - 在 Ruby 中动态生成多维数组 - 2

    我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常,但在我的实际使用中,我不会事先知道需要多少个数组。有一个更好的方法吗?谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]

  5. ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2

    如何只加载map边界内的标记gmaps4rails?当然,在平移和/或缩放后加载新的。与此直接相关的是,如何获取map的当前边界和缩放级别? 最佳答案 我是这样做的,我只在用户完成平移或缩放后替换标记,如果您需要不同的行为,请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail

  6. ruby - 动态方法链? - 2

    如何在对象上调用方法名称的嵌套哈希?例如,给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法,给定上面的散列,执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道,但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210

  7. ruby - 如何使用 method_missing 动态声明方法? - 2

    我有一个ruby​​程序,我想接受用户创建的方法,并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗?谢谢。编辑:我以不同的方式让它工作,但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method

  8. ruby - 动态扩展现有方法或覆盖 ruby​​ 中的发送方法 - 2

    假设我们有A、B、C类。Adefself.inherited(sub)#metaprogramminggoeshere#takeclassthathasjustinheritedclassA#andforfooclassesinjectprepare_foo()as#firstlineofmethodthenrunrestofthecodeenddefprepare_foo#=>prepare_foo()neededhere#somecodeendendBprepare_foo()neededhere#somecodeendend如您所见,我正在尝试将foo_prepare()调用注入

  9. ruby - 使用 jbuilder 创建具有动态哈希键的 JSON - 2

    这里我想输出带有动态组名的json而不是单词组@tickets.eachdo|group,v|json.group{json.array!vdo|ticket|json.partial!'tickets/ticket',ticket:ticketend}end@ticket是这样的散列{a:[....],b:[.....]}我想要这样的输出{a:[.....],b:[....]} 最佳答案 感谢@AntarrByrd,这个问题有类似的答案:JBuilderdynamickeysformodelattributes使用上面的逻辑我已经

  10. ruby - 在 Rakefile 中动态生成 Rake 测试任务(基于现有的测试文件) - 2

    我正在根据Rakefile中的现有测试文件动态生成测试任务。假设您有各种以模式命名的单元测试文件test_.rb.所以我正在做的是创建一个以“测试”命名空间内的文件名命名的任务。使用下面的代码,我可以用raketest:调用所有测试require'rake/testtask'task:default=>'test:all'namespace:testdodesc"Runalltests"Rake::TestTask.new(:all)do|t|t.test_files=FileList['test_*.rb']endFileList['test_*.rb'].eachdo|task|n

随机推荐