区块链技术博客
www.b2bchain.cn

打家劫舍三部曲DP

这篇文章主要介绍了打家劫舍三部曲DP,通过具体代码讲解8230并且分析了打家劫舍三部曲DP的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了打家劫舍三部曲DP。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8230.html。具体如下:

198. 打家劫舍  

打家劫舍三部曲DP

 

 class Solution {      //房屋不可以相邻 dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);      //前一个或者 前俩个状态转移过来  nums[i-1]     public int rob(int[] nums) {         if(nums==null||nums.length==0) return 0;         int len=nums.length;         int[] dp=new int[len+1];               dp[0]=0;         //1行房屋开始0号跳过         dp[1]=nums[0];         for(int i=2;i<=len;i++){             dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);         }         return dp[len];     } }

 

213. 打家劫舍 II  

打家劫舍三部曲DP

 

 class Solution {     //在1的基础上 不包含首 或者 不包含尾 分别计算比较最大值即可     public int rob(int[] nums) {        if(nums==null||nums.length==0) return 0;         int len=nums.length;        if(len==1) return nums[0];               int ans1=myRob(Arrays.copyOfRange(nums,0,len-1));        int ans2=myRob(Arrays.copyOfRange(nums,1,len));        return Math.max(ans1,ans2);     }     private int myRob(int[] nums){         if(nums==null||nums.length==0) return 0;         int len=nums.length;         int[] dp=new int[len+1];         dp[0]=0;         dp[1]=nums[0];         for(int i=2;i<=len;i++){             dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);         }         return dp[len];     } }

 

337. 打家劫舍 III  

 打家劫舍三部曲DP

 

 /**  * 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) {        int[] ans= dfs(root);        return Math.max(ans[0],ans[1]);     }     //0选1不选     private int[] dfs(TreeNode root){         if(root==null) return new int[]{0,0};         int[] leftVal=dfs(root.left);         int[] rightVal=dfs(root.right);         //选择根节点         int choose= root.val+leftVal[1]+rightVal[1];         //不选择根节点 左右 各有 选和不选 取最大值         int noChoose=Math.max(leftVal[0], leftVal[1]) + Math.max(rightVal[0], rightVal[1]);         return new int[]{choose,noChoose};     } }

 

本文地址https://www.b2bchain.cn/8230.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 打家劫舍三部曲DP
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们