没有小偷比我更专业（打家劫舍）

标签：专业 nums int max 不取 小偷 打家劫舍 dp

一：写在前面

  动态规划真的很重要，无论大公司小公司都会涉及到。博主最近在秋招，遇到了两个打家劫舍的笔试题 ，或者说是变形题。4399的猜密码，给你一串数字，相邻2个数字不能一起用，让你计算出这串数字能获得的最大和。另外一个小公司的摘苹果，一排苹果树，每颗树上都有一定的苹果，相邻的两棵树不能摘，问你能摘的最多苹果数量是多少？

二：思考过程

 我们以原题打家劫舍为例，来一步一步推导出递推公式。

 

 

 

 

 

1）先定义dp数组并且明确其含义

     数组中的每个数字我们可以选择取或者不取。设取为1，不取为0。可以得出如下的二维数组。

     int dp[n][2]记录每个阶段的状态      dp[i][0]表示第i个物品不偷，当下的最⼤⾦额      dp[i][1]表示第i个物品偷，当下的最⼤⾦额      

2）递推公式

当前状态有两，dp[i][1]表示当前数取，那么当前数取的话能得到的最大值就是在前一个数的不取的基础上（相邻数不能同时取）再加上当前数的值。

  dp[i][1] = dp[i - 1][0] + nums[i];

dp[i][0]表示当前元素不取，能够获得的最大值为：max(前一个数取状态的最大值，前一个数不取状态的最大值)。

  dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);

3）完整代码

 1 class Solution { 
 2  public int rob(int[] nums) { 
 3      if (nums.length == 0) return 0; 
 4      int n = nums.length; 
 5      // dp[i][0]表示第i个物品没有选时的最⼤⾦额
 6      // dp[i][1]表示第i个物品选择时的最⼤⾦额
 7      int[][] dp = new int[n][2]; 
 8      dp[0][0] = 0; 
 9      dp[0][1] = nums[0]; 
10      for (int i = 1; i < n; ++i) { 
11      dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]); 
12      dp[i][1] = dp[i-1][0] + nums[i]; 
13  } 
14      return Math.max(dp[n-1][0], dp[n-1][1]); 
15  } 
16 }

 

标签：专业,nums,int,max,不取,小偷,打家劫舍,dp
From： https://www.cnblogs.com/YXBLOGXYY/p/16709966.html