[HOT 100]今日一练------打家劫舍

题目链接

https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked

思路

动态规划，动态转移方程主要取决于两种情况：

1. 偷这家，不偷上家
2. 不偷这家，偷或者不偷上家

由上述两种情况我们便可以得到我们的动态转移方程，在此之前我们先引入所需变量以便表示方程：

1. f[i]：表示选择偷这家时，能拿到的最大的钱
2. g[i]：表示选择不偷这家时，能拿到的最大的钱

因此我们可以将动态转移方程表示为：

1. f[i] = g[i-1] + nums[i]
2. g[i] = Math.max(f[i-1], g[i-1])

不过需要注意的时，在正式进行动态规划之前我们要先进行初始化：

1. f[0] = nums[0]
2. g[0] = 0

动态规划完成之后的结果会剩下最后一家，而对于最后一家来说我们有两种选择，偷或者不偷，因此我们只需要判断这两种方案哪个我们可以拿到最多的钱，即：Math.max(f[n-1]. g[n-1])

代码

class Solution { //动态规划 public int rob(int[] nums) { int n = nums.length; if(n == 0) return 0; //选择该数时和的最大值 int[] f = new int[n]; //不选择该数时和的最大值 int[] g = new int[n]; //初始化 f[0] = nums[0]; g[0] = 0; for(int i = 1; i < n; i++) { f[i] = g[i-1] + nums[i]; g[i] = Math.max(f[i-1], g[i-1]); } return Math.max(f[n-1], g[n-1]); } }