问题描述
给定一个数组，表示每个房间的金钱。有一个小偷要从这些房间中将金钱偷走，但是不能偷相邻的两个房间。问小偷能偷走的最大金钱数。题目链接：**点我**
样例输入输出
输入：[1,2,3,1]
输出：4
说明：小偷偷编号 0（金钱为1）和编号 2 （金钱为 3）的房间，总价值为 4
输入：[2,7,9,3,1]
输出：12
说明：小偷偷编号 0 （金钱为 2）、编号 2（金钱为 9）、编号为 4（金钱为 1）的房间，总价值 12
问题解法
用动态规划进行求解。假设用 dp[i] 表示从 0 到 i 的房间中，小偷能获取的最大价值。则动态转移方程为 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution
{
public int rob(int[] nums)
{
if (nums == null || nums.length == 0)
{
return 0;
}
if (nums.length == 1)
{
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++)
{
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
|