Java算法训练—小偷案例

---

前言

动态规划是一种算法技巧，先举一个例子：
  如何让一个四岁的小孩理解动态规划的思路？国外友人有这样一个例子：列出一个1+1+1+1+1+1+1+1=？的式子，让小孩回答，小孩思索数秒后会告诉你答案是8。随后在前面再多写一个+1，再提问答案是多少，小孩会瞬间告诉你是9，问小孩为什么这么快就能得到答案，他会告诉你，因为只需要再加一个1就可以了。
  这里面就包含了动态规划的思想：将待求解的问题分成若干个子问题，从子问题的求解得到原问题的解，而在这个过程中，已经求解过的子问题，其解是已经被记录下的，这样就能避免很多重复的计算。下面我们看一个具体的简单案例。

一、案例描述

ps：此题来源于力扣网站

  一个小偷准备挨家挨户进行偷窃，每一家都有一些能偷到的金额值，但是不能连续进入相邻的两间房屋，否则会被发现。将这个设定抽象成一个数组，每家拥有的金额组成一个非负的整型数组，在不被发现的情况下，计算小偷能偷到的最大数额。

例如[1,2,5,3,4,8,2]，那么最大值就是：第一家（1）+第三家（5）+第六家（8）=14.

二、问题分析

先来分析一些特殊情况：
①.假如只有一间房屋，那么小偷只能偷窃该房间，那么最大值就是该房间里的金额值。
②.假如有两间房屋，那么两间房屋里，哪间房屋的金额值高，其值就是小偷能偷到的最大值。

那么，当房间数量大于2时，由于小偷不能进入相邻的房间：
①.假如小偷进入了第x间房，则他必然没有进入x-1间房，最高金额sum就等于前面x-2间房中的最大总金额值加上第x间房里的金额值。
②.假如小偷没有进入第x间房，那么最高金额sum就等于前面x-1间房里的最高总金额。

  于是，x任取的情况下，小偷进入第x间房屋和没有进入第x间房屋这两种情景就涵盖了这个案例的题解。
  即最高金额总值，就是这两种情况中的更大的那个值。用 sum[i] 来表示前 i 间房屋里能偷到的最大金额值，用cash [i]来表示第 i 间房里的金额，根据上面的分析可以得到下面的关系式（状态转移方程）：

sum[i] = max(sum[i-2]+cash[i] , sum[i-1])

再把前面分析的特殊情况作为边界条件考虑进去：

①. sum[0] = cash[0] ---------------------------房间数为1时
②. sum[1] = max(cash[0] ,cash [1]) ------ 房间数为2时

这样，假设有n间房屋，那么最后总值数组中的最大值就是 sum[n-1] .

三、代码示例

将上述的思路转化为代码如下：

public static int rob(int[] cash) {//数组为0，表示房间数为0，那么最高金额自然也是0if (cash.length == 0 || cash == null) {return 0;}//一间房屋的情况，该房间内的金额就是最大值，直接返回该值if (cash.length == 1) {return cash[0];}//创建一个用于存储最大总和值的数组 sumint len = cash.length;int[] sum = new int[len];//给定sum的边界条件，房间数为1和2时sum[0] = cash[0];sum[1] = Math.max(cash[0], cash[1]);//从房间数为3开始，最大总值数组的每一个元素值应该满足以下的状态转移方程for (int i = 2; i < len; i++) {sum[i] = Math.max(sum[i - 2] + cash[i], sum[i - 1]);}//遍历完数组，也就找到了最大值.return sum[sum.length - 1];}

测试上述方法，比如就将我们前面列举的数组[1,2,5,3,4,8,2]代入方法里。

public static void main(String[] args) {int[] cash = {1,2,5,3,4,8,2};int x = rob(cash);System.out.println("小偷能偷到的最大金额为："+x);}

运行结果如下：

总结

  这就是一个简单的案例，解题方法体现了动态规划的思想。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。这时候将问题分成很多子问题，并且求出子问题的解，用一个容器（本例中的数组）来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果记录在容器中，避免重复计算，这就是动态规划法的基本思路。