算法记录

LeetCode 题目：

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

&emsp;&emsp;给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明

一、题目

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

二、分析

题目中说所有的房屋连接在一起是成环的，也就意味着选了第一间屋子那么就不能够选最后一间屋子了，不选第一件屋子就可以选最后一间屋子，因此需要进行两次计算。

因为它存在一个最大金额这样的一个结果，而最优解我们不妨使用动态规划来套一下，首先建立动态转移方程。

如果不偷当前的房屋，那么此时的金额是多少呢。肯定是前一个屋子没有偷或者是偷了的最大值，因为题目中说过所有的金额都是正的，因此不可能涉及到更前面的屋子情况。

如果偷当前的房屋，那么此时的金额是多少呢。因为两间屋子不能同时被偷，那么肯定由前一间没偷和前两间偷了的最大值再加上偷了这一间的值。这里为什么不用前两间没偷的值来计算呢，因为前两间没偷的值肯定会被前一间偷了的情况所使用的，而前一间被偷的情况会被当前间没被偷所使用的，故此不在用于重复计算。

class Solution {    public int rob(int[] nums) {        int len = nums.length;        if(len == 1) return nums[0];        if(len == 2) return Math.max(nums[0], nums[1]);        return Math.max(caculate(nums, 0, len - 2), caculate(nums, 1, len - 1));    }    public int caculate(int[] nums, int start, int end) {        int[][] temp = new int[nums.length][2];        temp[start][1] = nums[start];        temp[start + 1][1] = nums[start + 1];        temp[start + 1][0] = nums[start];        for(int i = start + 2; i <= end; i++) {            temp[i][0] = Math.max(temp[i - 1][1], temp[i - 1][0]);            temp[i][1] = Math.max(temp[i - 2][1], temp[i - 1][0]) + nums[i];        }        return Math.max(temp[end][0], temp[end][1]);    }}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

状态转移方程的定义。

原文：https://juejin.cn/post/7100154677865971743