vlambda博客
学习文章列表

动态规划经典题目很多，这里一起分析一个经典的求数组所有非相邻数字和最大值。这个问题有很多变种问题如：

• 按摩师
  一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
  给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
  来源：力扣（LeetCode）- the-masseuse-lcci

• 打家劫舍
  你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
  给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
  来源：力扣（LeetCode）- house-robber

• 拿糖果
  小明要在街上一排互相相邻的糖果屋拿糖，但不能在两个相邻的糖果屋同时拿糖。给定一个数组列表，每个元素代表每间房子中的糖的数目，小明一次最多能拿多少糖。
  例：输入: [1,5,3,1,7]
  输出: 12

• 寿司摆盘
  给你一堆寿司 不能选相邻的盘子 然后要选出价格加起来最高的那些 print价格
  例1：[9 1 4 3] 输出13
  例2：[9 1 3 2 5] 输出17

• 求数组不相邻元素之和的最大值
  例1：arr = [1, 2, 3, 4, 5]
  不相邻最大: 3 + + 5 + 1 = 9
  例2: arr = [2, 4, 1, 6, 7]
  不相邻最大: 4 + 7 = 11

• 其他类似

思路分析

动态规划问题一般解题思路：
1、明确基本条件下的结果baseCase，既递归出口
2、明确状态转移方程
3、定义函数

baseCase

  求数组中不相邻元素和的最大值的基本出口是当数组元素只有1个的时候arr[0],2个元素的时候max(arr[0],arr[1])。

状态转移方程

  数组中不相邻元素和的最大值，以arr = [2, 4, 1, 6, 7]为例，数组总共有5个元素，如果我们选择最后一个元素的话，最大值等于 arr[4]（数组下标从0开始） + max(前4个元素不相邻的最大和)，如果不选最后一个元素的话，最大值等于max(前4个元素不相邻的最大和)，最终在这两种情况中取最大值。

简化伪代码表示为：

以如下前n个元素的最大值,opt表示前n个元素的不相邻最大和,伪代码如下：
function opt(arr,n){
    if(n == 0) => arr[0]
    else if(n == 1) => max(arr[0],arr[1])
    else => max(arr[n] + opt(n-2),opt(n-1))
}

代码实现（递归，自顶向下）

public static void main(String[] args) { int[] arr = {2, 4, 1, 6, 7}; System.out.println(optimizeRec(arr,arr.length - 1)); System.out.println(optimizeForEach(arr)); }  /** * 自顶向下，递归，确定递归出口 */ private static int optimizeRec(int[] arr,int n){ //如果只有一个元素 取自己 if(n == 0){ return arr[0]; } //如果有两个元素，取其中最大 if(n == 1){ return Math.max(arr[0],arr[1]); } //递归：取当前和取前一个的最大 //取当前 只能取他的隔一个的元素 //Max(optimizeRec(n-2) + arr[n],optimizeRec(arr,n-1)) return Math.max(optimizeRec(arr,n-2) + arr[n],optimizeRec(arr,n-1)); }

代码实现（循环，自底向上）

上面递归的方式实现有个问题，出现了重复子问题，的时候多次进行了计算。这时候可以使用记忆表的方式，将计算过的数据进行存储，后续用的额时候取出来直接用即可。因此可以用一个自底向上的一个遍历的方式

public class NonContiguousArraySumMax {
 public static void main(String[] args) { int[] arr = {2, 4, 1, 6, 7}; System.out.println(optimizeRec(arr,arr.length - 1)); System.out.println(optimizeForEach(arr)); }
 /** * 自顶向下，递归，确定递归出口 */ private static int optimizeRec(int[] arr,int n){ //如果只有一个元素 取自己 if(n == 0){ return arr[0]; } //如果有两个元素，取其中最大 if(n == 1){ return Math.max(arr[0],arr[1]); } //递归：取当前和取前一个的最大 //取当前 只能取他的隔一个的元素 //Max(optimizeRec(n-2) + arr[n],optimizeRec(arr,n-1)) return Math.max(optimizeRec(arr,n-2) + arr[n],optimizeRec(arr,n-1)); }
 /** * 自底向上，循环推演，从基本情况开始 */ private static int optimizeForEach(int[] arr){ int len = arr.length; if(len == 0){ return 0; } int[] maxArr = new int[len]; for (int i = 0;i < len ;i++){ if(i == 0){ //如果只有一个元素 取自己 maxArr[0] = arr[0]; }else if(i == 1){ //如果有两个元素，取其中最大 maxArr[1] = Math.max(arr[0],arr[1]); }else{ maxArr[i] = Math.max(maxArr[i-2] + arr[i],maxArr[i-1]); } } return maxArr[len - 1]; }}