一道简单题目,DP 的递归表示竟然无法 AC,只能用递推表示。解题思路:
* @Description nums 长度决定为题规模
* 按 nums 长度区间进行分治
* G(i) 代表前 i 个元素中可得的最大分钟数
* 因为题目要求,相邻元素不能选取,所以要确定 G(i-1) 与 G(i) 的关系,我们还需要知道 i-1 是否有被选取到
* 我们改变一下 G(i) 的含义,使其表示选取的最后一个元素为 i 时,可获取的最大分钟数
* 最优解的组合,必然被包含在某个 0~i 之间的元素为被选取的最后一个元素的情况中,所以该定义可以覆盖解空间
* 此时列出状态转移方程:
* G( i )= max { G(i-2) + nums[i+1],G(i-1) }
* 回归条件:
* 当 i 分解到 0 时,G(i) 从 nums[0] 回归;当 i 分解到 1 时 ,从 max ( nums[0] , nums[1] ) 回归
递归表示:
public final int massage(int[] nums, int flag, int[] cache) { if (flag == 0) { return 0; } if (flag == 1) { return Math.max(nums[0], nums[1]); } if (cache[flag] != 0) { return cache[flag]; } int beforeOne = massage(nums, flag - 1, cache); int beforeTwo = massage(nums, flag - 2, cache) + nums[flag]; cache[flag] = Math.max(beforeOne, beforeTwo); return cache[flag]; }
递推表示:
public final int massage(int[] nums) { int length = nums.length; if (length == 0) { return 0; } if(length==1){return nums[0];} int[] cache = new int[length]; cache[0] = nums[0]; cache[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { cache[i] = Math.max(cache[i - 1], cache[i - 2] + nums[i]); } return cache[length - 1]; }
递归超时,递推效果: