在动态规划1中，上楼梯问题已经被解决了，上楼梯的本质是一个尾递归，因此可以被转换成循环，但是并不是所有的动态规划都拥有尾递归的特征，我们再来看看另一个题目；

题目

打劫，{1，2，3，4，5}，这个数组中的每一个元素代表着一个屋子中的财产数量，在打劫的时候不能打劫相邻两个屋子中的财物，请问如何计算一趟打劫最多能打多少钱；

解析

就像爬楼梯一样，想要到达n阶，就一定得到达n-1或者n-2阶；
打劫的时候，如果打劫了第n家，那么n-1家一定不能去染指…
化简一下这个数组：

  1. 当只有一间房子的时候，抢劫的最大收益就是1；
  2. 当{1，2}的时候，打劫的最高值是2；这个时候，问题就可以变成：是否偷窃第二间房屋？如果偷窃，那么就不能偷窃第1间；相反的如果不偷第2间，那么只能偷窃第1间，结果变成了max{1,2}；此时最优收益为2；
  3. 当{1，2，3}的时候，打劫的最高值是4；同样把问题化解为是否偷窃第3间，如果偷了，那么就不能偷窃第2间房屋中的财物，如果不偷窃，就可以偷第2间房屋中的财物max{偷第2间，偷第1间+偷第3间}
  4. 当{1，2，3，4}的时候，打劫的最高值是6；max{偷第3间，偷第2间+偷第4间}；

递推…当到第n间的时候，偷窃的最高金额数量=max{偷第n-1间，偷n-2间+偷第n间}；此时就可以使用递归完成整个过程，将偷窃每一间能获取的最大金额数记录下来，然后递归到最后一个房间做决定即可；

编码

  1. import java.util.Arrays;
  2. class Solution {
  3.     private boolean arrayInitFlag=false;
  4.     private int[] maxMoney;
  5.     private int[] home;
  6.     public int rob(int[] nums) {
  7.         if(nums.length==0)
  8.             return 0;
  9.         if(nums.length==1)
  10.             return nums[0];
  11.         if(nums.length==2)
  12.             return nums[0]>nums[1]?nums[0]:nums[1];
  13.         if(arrayInitFlag==false)
  14.         {
  15.             home=nums;
  16.             //执行初始化，赋予1，2两个房间的最大值
  17.             maxMoney = new int[nums.length+2];
  18.             Arrays.fill(maxMoney,-1);
  19.             maxMoney[1]=nums[0];
  20.             maxMoney[2]= nums[0]>nums[1]?nums[0]:nums[1];
  21.             arrayInitFlag=true;
  22.         }
  23.         return steal(nums.length);
  24.     }
  25.     private int steal(int homeCode)
  26.     {
  27.         if(maxMoney[homeCode-1]==-1)
  28.         {
  29.             maxMoney[homeCode-1] = steal(homeCode-1);
  30.         }
  31.         if(maxMoney[homeCode-2]==-1)
  32.         {
  33.             maxMoney[homeCode-2] = steal(homeCode-2);
  34.         }   
  35.         if(maxMoney[homeCode-1]>maxMoney[homeCode-2]+home[homeCode-1])
  36.         {
  37.             //表示不偷窃这间的收益更大
  38.             return maxMoney[homeCode-1];
  39.         }
  40.         else
  41.             return maxMoney[homeCode-2]+home[homeCode-1];
  42.     }
  43. }

假设要判断是否偷第4间:{1,2,3,4}为例；

  1. 执行steal(4)，maxMoney[3]（4-1）不存在；开始套娃；
  2. 执行steal(3)，homeCode=3；maxMoney[2]（3-1）存在；继续向下执行，maxMoney[1]（3-2）也存在；此时比较maxMoney[3-2]+home[2]（偷第1间和第3间）和maxMoney[2]（偷第2间），4>2，返回4；
  3. 回到steal(4)中，继续向下执行，maxMoney[3]被赋值为4；
  4. 在steal(4)中，继续向下执行，maxMoney[2]存在，内容为2；
  5. 判断2+4和4的大小，很明显2+4更大，返回数值6；