问题描述
地址
问题分析
这道题不难，本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。最优化问题。很明显用动态规划求解。但是有一点比较有意思，如果对状态定义的不同，算法时间复杂度不同如果 dp[i] 表示 [i ~ n-1] 中的最大和，那么状态转移条件为 dp[i] = Math.max(nums[j] + nums[j + 2]) 其中i <= j < n - 1，因为需要枚举j,是一个O(N^2)的时间复杂度。如果 dp[i] 表示 [0 ~ i] 中的最大和，那么状态转移条件为 dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]),这是一个 O(N) 的时间复杂度，并且如果对空间优化，是一个 O(1) 的空间复杂度
经验教训
动态规划中状态定义的意义不同，有可能会造成算法复杂度的不同
代码实现
状态定义1
public
int rob(
int[] nums) {
if (nums == null || nums.
length ==
0) {
return 0;
}
int[] dp = new
int[nums.
length];
dp[nums.
length -
1] = nums[nums.
length -
1];
for (
int i = nums.
length -
2; i >=
0; --i) {
int max =
0;
for (
int j = i; j < nums.
length; ++j) {
max = Math.
max(
max, nums[j] + (j +
2 < nums.
length ? dp[j +
2] :
0));
}
dp[i] =
max;
}
return dp[
0];
}
状态定义2
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], nums[i] + dp[i -
2]);
}
return dp[nums.
length -
1];
}
状态定义2空间优化
public
int rob(
int[] nums) {
if (nums == null || nums.
length ==
0) {
return 0;
}
if (nums.
length ==
1) {
return nums[
0];
}
int pre = nums[
0];
int cur = Math.
max(nums[
0], nums[
1]);
for (
int i =
2; i < nums.
length; ++i) {
int temp = cur;
cur = Math.
max(cur, nums[i] + pre);
pre = temp;
}
return cur;
}
