# 动态规划（二）之打家劫舍

相信经过上一期坏蛋哥详细的讲解，小伙伴们对一般的动态规划已经有了初步的认识，记得我刚接触动态规划的时候，一直都问自己一个问题，为什么这类算法叫动态规划呢？有什么含义?相信爱思考的小伙伴们也有这个疑问，我的答案是让递归有记忆，根据以往的记忆动态规划下一步。如果你有更好的解释，记得后台联系坏蛋哥哦。如果你也喜欢坏蛋哥的内容，记得关注加👍哦。

题目内容

原题获取链接：https://leetcode-cn.com/problems/house-robber-iii/

是不是感觉现在小偷的智商都这么的高，还是一个计算机专家（是你吗？哈哈）。

小偷：咱们这职业不是谁想当就能当的，咱们是专业的。

题解思想

这是我跑出来的效果：期待小伙伴的超越哦（有点飘了）。

思想还是用的前面打家劫舍一和二的思想（动态规划）

只是把辅助数组，换成了树节点中的val变量，甚至运行内存可以通过迭代后序遍历的思想还能减少部分的消耗。

最后的时间复杂度为 O(n)，空间复杂度为O(1)，这儿其实可以不改变val变量的值，有余力的小伙伴可以思考一下。

题解主要的思想还是动态规划的选和不选：

如果选了i节点，那么i的子节点就不能选，最多还能选i子节点的子节点及它们的孩子。那么就可以在选了i的情况下的最大值和没有选i的情况下的最大值进行比较，谁大，就说明这个树的最大偷取的money为多少。

转移方程（假设左节点，右结点及他们的孩子都存在）为：

dp[i]=max(f(i)+dp[i->l->l]+dp[i->l->r]+dp[i->r->l]+dp[i->r->r],dp[i->l]+dp[i->r])

符号定义解释：

1️⃣dp[i]表示以i为根结点的子树的最大偷取的money。

2️⃣dip[i->l->l] 如果i的左节点的左节点存在，那么以i左节点的左节点为根的子树所能偷取的最大值，同理其他符号类似。

3️⃣f(i) 表示i节点中的val变量的大小。

因为动态规划要选择计算的方向，如果从根往下面计算，那么会存在很多lamp sub-problem，这正是动态规划所要解决的问题，所以我们就要思考如何从根往上算，那么在树的遍历中，后序遍历恰好可以满足在算根的时候，子树已经算好了。

具体实现代码:

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 * int val;

 * TreeNode left;

 * TreeNode right;

 * TreeNode(int x) { val = x; }

 * }
   */
   class Solution {
       public int rob(TreeNode root) {
       //判断是否为null
       if(root!=null)
       {
           if (root.left!=null) {
               rob(root.left);
           }
           if (root.right!=null){
               rob(root.right);
           }
           //然后计算该结点的最大值，前提是上面的左右结点已经计算
           coculate(root);
           return root.val;
       }else {
           return 0;
       }

   }

   public void coculate(TreeNode node){
       //定义两个变量
       int choice=0;    //选node
       int nochoice=0;  //不选node
      
       //特判
       if (node==null)
           return;
       else
           choice=node.val;
      
       //计算node的左子树
       if (node.left!=null){
           nochoice+=node.left.val;
           if (node.left.left!=null){
               choice+=node.left.left.val;
           }
           if (node.left.right!=null){
               choice+=node.left.right.val;
           }
       }

       //计算node的右子树
       if (node.right!=null){
           nochoice+=node.right.val;
           if (node.right.left!=null){
               choice+=node.right.left.val;
           }
           if (node.right.right!=null){
               choice+=node.right.right.val;
           }
       }
      
       //返回选不选node的各自情况下最大的money
       node.val=choice>nochoice?choice:nochoice;

      }
   }
  

总结

经过这一期内容的分享，相信小伙伴们已经对动态规划有了一个比较直观的感受了。无论是面试还是考研考取好的学校，相信算法的熟稔能让你们更加出彩出众。期待你们的进步。

永远做爱学习的小白。我是坏蛋哥，咱们下期再会。