[数据结构与算法]经典动态规划+实例题实战（注解）

? ? ? ? ? 动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。同时，我们也可以对动态规划进行空间压缩，起到节省空间消耗的效果。
?

? ? ? ? 题目：假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。

? ? ? ? 题解：首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k~(k>2)k?(k>2) 间房屋，有两个选项：

偷窃第 k间房屋，那么就不能偷窃第 k?1 间房屋，偷窃总金额为前 k?2 间房屋的最高总金额与第 k?间房屋的金额之和。此题的：first+nums[i]

不偷窃第 k?间房屋，偷窃总金额为前 k?1 间房屋的最高总金额。此题的：second

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 kk 间房屋能偷窃到的最高总金额。

class Solution {
    public int rob(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;//首先判断特殊情况为0
        }
  int length=nums.length;
  if(length==1){
      return nums[0];//只有一间房直接返回
  }

  int first=nums[0];//记录第一间房的钱，这里用到了空间压缩
  int second=Math.max(nums[0],nums[1]);//记录二间房的最大钱
  for(int i=2;i<length;i++){
      int temp=second;//把最大的钱给temp
      second=Math.max(second,first+nums[i]);//second表示不抢第i间的最大钱，后者表示抢i间的钱，两者取最大给secod
      first=temp;//把second给first，就这样轮番传递，像队列一样一个一个出
  }
  return second;//返回最大的值
}
}