电子商务网站建设规划范文,微信小程序开发案例教程,西安网站开发公司排行榜,创建一个网站描述
你是一个经验丰富的小偷#xff0c;准备偷沿街的一排房间#xff0c;每个房间都存有一定的现金#xff0c;为了防止被发现#xff0c;你不能偷相邻的两家#xff0c;即#xff0c;如果偷了第一家#xff0c;就不能再偷第二家#xff1b;如果偷了第二家#xff0…描述
你是一个经验丰富的小偷准备偷沿街的一排房间每个房间都存有一定的现金为了防止被发现你不能偷相邻的两家即如果偷了第一家就不能再偷第二家如果偷了第二家那么就不能偷第一家和第三家。
给定一个整数数组nums数组中的元素表示每个房间存有的现金数额请你计算在不被发现的前提下最多的偷窃金额。
数据范围数组长度满足 1≤n≤2×105数组中每个值满足 1≤num[i]≤5000
示例1
输入
[1,2,3,4]
返回值
6说明
最优方案是偷第 24 个房间
示例2
输入
[1,3,6]
返回值
7说明
最优方案是偷第 13个房间
示例3
输入
[2,10,5]
返回值
10说明
最优方案是偷第 2 个房间 思路分析
该题使用动态规划来解决
具体做法
step 1用dp[i]表示长度为i的数组最多能偷取到多少钱只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。step 2初始状态 如果数组长度为1只有一家人肯定是把这家人偷了收益最大因此dp[1]nums[0]。step 3状态转移 每次对于一个人家我们选择偷他或者不偷他如果我们选择偷那么前一家必定不能偷因此累加的上上级的最多收益同理如果选择不偷他那我们最多可以累加上一级的收益。因此转移方程为dp[i]max(dp[i−1],nums[i−1]dp[i−2])。这里的i在dp中为数组长度在nums中为下标。
图示 代码
import java.util.*;public class Solution {/*** param nums int整型一维数组 * return int整型*/public int rob (int[] nums) {int[] dpnew int[nums.length1];dp[1]nums[0];for(int i2;inums.length;i){dp[i]Math.max(dp[i-1],nums[i-1]dp[i-2]);}return dp[nums.length];}
}
