C语言打家劫舍问题怎么解决

本篇内容介绍了“C语言打家劫舍问题怎么解决”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

成都创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站制作、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的长沙县网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

原题

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。

解题

这道题的变化是,同样是一个数组,但是首尾相连了,也就是成了一个环,那么原本递推的方式也就行不通了,因为任何一个节点其实地位都相等了,也就找不到最初的状态,无法进行递推了。

但我们可以将现在的问题转化成我们已经解决的问题,仔细想想。所谓的首尾相连,针对状态进行划分,可以有三种情况:

  1. 首尾节点都不选择

  2. 只选择首节点,不选择尾结点

  3. 只选择尾结点,不选择首节点

因为我们最终是要求出最大值,那么只需要考虑后面两种情况,而这样的话,又可以转化成了原本的线性数组了。

接下来让我们看看代码:

class Solution {
   public int rob(int[] nums) {
       if (nums.length == 0) {
           return 0;
       }

       if (nums.length == 1) {
           return nums[0];
       }

       // 因为收尾相连,无法按照最初的动态规划来做,因为没有一个可以开始的点。
       // 那么就将未知问题转化为已知问题,针对首尾两个节点,可以有三种情况:
       // 1、首尾节点都不选择
       // 2、只选择首节点,不选择尾结点
       // 3、只选择尾结点,不选择首节点
       // 因为是要取最大值,且是非负整数数据,所以只考虑后两种情况

       return Math.max(
           // 只选择首节点,不选择尾结点
           calMax(nums, 0, nums.length - 2),
           // 只选择尾结点,不选择首节点
           calMax(nums, 1, nums.length - 1)
       );
   }

   public int calMax(int[] nums, int start, int end) {
       // 存储当前位置,下一个位置,和再下一个位置的结果
       int current = 0;
       int next_1 = 0;
       int next_2 = 0;
       // 动态规划,利用中间结果,寻找最大值
       for (int i = end; i >= start; i--) {
           current = Math.max(
               // 当前不偷
               next_1,
               // 当前偷
               nums[i] + next_2
           );
           next_2 = next_1;
           next_1 = current;
       }
       return current;
   }
}

“C语言打家劫舍问题怎么解决”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!


当前文章:C语言打家劫舍问题怎么解决
当前路径:http://scyanting.com/article/poeiid.html