题目描述
一列房屋按顺序排列，每个屋子里有一定的钱，不能同时偷两个相邻的屋子，否则会触发警报，问在不触发警报时，能偷到的最多的金额。
关键点在于不能同时选择相邻的2个屋子。
考虑用动态规划来做。
第一版动规
设状态f[i]表示，只从前i个屋子里偷，能偷到的最高金额。
接下来考虑状态转移，对f[i]进行情况划分。我们分为
- 偷第
i个房屋 - 不偷第
i个房屋
若偷i，则不能偷i - 1；若不偷i，则可以偷i - 1
考虑用f[i][1]表示，只从前i个屋子偷，并且偷i，能得到的最高金额；用f[i][0]表示，只从前i个屋子偷，并且不偷i，能得到的最高金额。
于是，状态转移方程就比较简单了，
f[i][1] = f[i - 1][0] + nums[i - 1]（f下标从1开始，数组下标从0开始）
f[i][0] = max {f[i - 1][0], f[i - 1][1] }
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[][] f = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + nums[i - 1];
}
return Math.max(f[n][0], f[n][1]);
}
}
第二版动规
其实不需要二维数组，一维即可
- 当偷
i时，i - 1不能偷，只能从前i - 2中偷，则
此时f[i] = f[i - 2] + nums[i - 1] - 当不 偷
i时，i - 1可以偷，则
此时f[i] = f[i - 1]
二者取个最值即可
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] f = new int[n + 1];
f[1] = nums[0];
for (int i = 2; i <= n; i++) {
f[i] = Math.max(nums[i - 1] + f[i - 2], f[i - 1]);
}
return f[n];
}
}
第三版动规
使用滚动数组思想优化，把空间复杂度降为 O ( 1 ) O(1) O(1)
对每一个i，只需要记录i - 1和i - 2的f即可，用3个变量来循环更新就行了
class Solution {
public int rob(int[] nums) {
int a1 = 0, a2 = nums[0], a3 = nums[0];
for (int i = 2; i <= nums.length; i++) {
a3 = Math.max(nums[i - 1] + a1, a2);
a1 = a2;
a2 = a3;
}
return a3;
}
}
打印最优解的路径
开个数组，记录一下每一个状态是由哪一个先前的状态转移过来的即可
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] f = new int[n + 1];
int[] pre = new int[n + 1]; // 当前这个位置有没有被纳入
f[1] = nums[0];
pre[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = Math.max(nums[i - 1] + f[i - 2], f[i - 1]);
if (f[i] != f[i - 1]) pre[i] = 1;
}
List<Integer> path = new ArrayList<>();
int i = n;
while (i > 0) {
if (pre[i] == 1) {
path.add(i);
i -= 2;
} else i--;
}
for (i = path.size() - 1; i >= 0; i--) {
System.out.println(path.get(i) - 1);
}
return f[n];
}
}
