动态规划（一）之打家劫舍

做过算法题的小伙伴应该都知道动态规划吧，它无论是在ACM比赛还是在各大公司面试中都占有非常高的比重，可想而知动态规划在算法题中的地位。坏蛋哥在一开始就可以告诉小伙伴们，动态规划的题难的话可以非常难，简单的也可以so easy 的做出来，所以我分享的一般都是经典的题目，能把经典的吃透，再去挑战难度更大的肯定事半功倍。

今天分享的两个主角是打家劫舍（一）和打家劫舍（二）。爱问问题的小伙伴就要问了：那有没有打家劫舍（三）呢.......哈哈，那肯定是有的啦，不然怎么对得起坏蛋哥这讲解的智商呢（低调！）

动态规划的核心思想

说到动态规划，就不得不提一下递归了，坏蛋哥认为动态规划就是对递归的一种时间复杂度的优化，学过基本的算法的小伙伴肯定知道，要换取时间复杂度，那么很大可能就是要牺牲空间复杂度。是的，你没有听错。它的本质也就是用空间来换取时间。

动态规划重要的几个点：

1️⃣ 子问题（lamp sub-problem），也就是如何把一个复杂的问题分解。这儿也就引出了动态规划的重头戏--转移方程，后面我会讲解什么是转移方程

2️⃣ 数组，在动态规划的算法中，一般是用数组来作为辅助存储。所以我们要选择一个合适的辅助数组（比如是一维还是二维，数组的长度等等）

3️⃣ 计算顺序，举个简单的栗子：大家都应该知道斐波那契数列（Fibonacci sequence）吧，它是这样一个数列：0、1、1、2、3、5、8、13、21、34、……。是不是有这样的规律 f(i)=f(i-1)+f(i-2)，i是数组的下标。试想如果我们先计算f(6),那么就要递归等待f(5)和f(4),然而f(5)又要递归f(4)和f(3)。是不是f(4)需要被递归多次。如果在f(i)非常大的时候，那么时间复杂度就会非常的高。但是我按照f(1),f(2),f(3)的顺序依次计算，结果又会怎样呢？很显然嘛，时间复杂度变为了O(n)。可想而知计算顺序的重要性。

4️⃣ 初始化，在后面的例子中坏蛋哥会解释这个过程。

有了上面的知识储备，那么就让我们实际来解题试试（疗效好不好，事实说了算）

打家劫舍一

这道题是leetcode上面比较经典的动态规划题，获取原题（https://leetcode-cn.com/problems/house-robber/）

在解动态规划算法的时候，某些题正好是选与不选的概念。

具体解释是这样的，我们换一种思路：我们要得到最大值，是不是就涉及到一个“选与不选”的概念，比如说上面有四个元素，我们依次标为a[0]，a[1]，a[2]，a[3]。是不是我选了a[3]，就不能选a[2]了，就只能选a[1]和a[1]之前的元素呢？

本题的题解思路：

1️⃣ 找出转移方程（又一个大的状态转移到一个小的状态）：dp[i]=max( f(i) + dp[i-2] ,dp[i-1] )    

注：解释一下参数：dp[i] 表示0~i的数组偷取的最大money,f(i)便是第i个元素可以偷取的money。

2️⃣ 计算方向：很显然这个问题类似于斐波拉契数列，如果从后往前，那么是需要递归的，如果从前往后，那么就是一条路算到底。复杂度就变为了O(n)。

3️⃣  初始化：既然是从前往后，但是第一个元素的前两个元素怎么表示呢？ 其实做法很简单，将数据前面加两个值为0的元素不就解决问题了吗。

流程拉通下来，小伙伴们是不是感觉原来都是套路啊！

是的，但是也有不按套路出牌的，但是是少数哦，那些能难到你怀疑人生。

最后我们就看一下具体的代码：

import static java.lang.Math.max;
class Solution {
public int rob(int[] nums) {
        //特判
        if (nums==null && nums.length==0){
            return 0;
        }
        
        //初始化变量
        int[] maxMoney=new int[nums.length+2];
        
        //开始计算
        for (int i=0;i<nums.length;i++){
            //maxMoney的i+2与nums相对应
            maxMoney[i+2]=max(maxMoney[i]+nums[i],maxMoney[i+1]);
        }
        
        return maxMoney[maxMoney.length-1];
    }
}

get到了吗，是不是感觉坏蛋哥的讲解这么的到位。是不是有想👍的冲动。

打家劫舍（二）

完成上面的练习，那恭喜你们，已经获得解决动态规划的一个概念，那么剩下就是通过更多的题目来体会上面的要点。那么我们就继续打家劫舍（哈哈，坏蛋哥是个好人，不是真的要打家劫舍哈。）

甩出题目：如需原题，请访问https://leetcode-cn.com/problems/house-robber-ii/

这道题怎么做呢，感觉又要掉好多头发。哈哈，我们需要结合偷前面的money的经验哦（毕竟小偷这个职业也需要汲取历史的经验嘛）。

我们是否单独考虑最后一个元素呢，如果选择最后一个元素，那么就不能选择第一个和最后一个的前一个元素。如果不选呢？是不是从第一个到倒数第二个就是和打家劫舍一相同了。是的，通过上面的分析，我们就讲问题转换为上一个问题了。

具体题解代码：

package com.yunhai.leetcode.dynamic_prgraming;


import static java.lang.Integer.max;

/**
 * function:实现打家劫舍二
 * 打家劫舍二可以转换为打家劫舍二，当最后一个元素选择时，那么就从1到（n-2）为劫舍一的问题
 * 当最后一个元素不要的时候，那么就是从0到n-1为劫舍二的问题
 *
 */
public class Rob213 {
    public int rob(int[] nums) {
        int len = nums.length;
        int maxMoney = 0;

        //特判
        if (len <= 3) {
            if (len == 0) {
                maxMoney = 0;
            } else {
                for (int i = 0; i < len; i++) {
                    maxMoney = max(maxMoney, nums[i]);
                }

            }
            System.out.println("长度小于三，且maxMoney为：" + maxMoney);
            return maxMoney;
        }

        //将问题拆分
        int[] eliminateFinal = new int[len - 1 + 2]; //前面加两个辅助元素，并都置为0
        int[] choseFinal = new int[len - 2 + 2];

        //初始化
        eliminateFinal[0] = eliminateFinal[1] = 0;
        choseFinal[0] = choseFinal[1] = 0;

        //开始计算elimateFinal 0到n-1
        for (int i = 0; i < len - 1; i++) {
            eliminateFinal[i + 2] = max(nums[i] + eliminateFinal[i + 2 - 2], eliminateFinal[i + 2 - 1]);
            System.out.print(eliminateFinal[i+2]+"\t");
        }

        System.out.println();

        //开始计算choseFinal 1到n-2
        for (int i = 1; i < len - 2; i++) {
            choseFinal[i - 1 + 2] = max(nums[i] + choseFinal[i + 2 - 2 - 1], choseFinal[i + 2 - 1 - 1]);
            //上面之所以要减一，是因为i是重1开始的
            System.out.print(choseFinal[i-1+2]+"\t");
        }
        System.out.println();
        //System.out.println(eliminateFinal[len - 2 + 2]+"##"+choseFinal[len - 4 + 2] + nums[len - 1]);


        //比较最后的结果
        return max(eliminateFinal[len - 2 + 2], choseFinal[len - 4 + 2] + nums[len - 1]);


    }

    /**
     * 测试：
     *{1,2,1,1};
     *
     * @param args
     */
    public static void main(String[] args){
        int[] test={1,3,1,3,100};
        Rob213 rob213=new Rob213();
        System.out.println(String.format("结果为:%d", rob213.rob(test)));
    }
}

总结

相信经过上面坏蛋哥经典（垃圾）的讲解，小伙伴们已经会解决一般的动态规划的问题，坏蛋哥其实挺喜欢刷动态规划的题，因为他真的有时候很操蛋（难到要死），但是看了大神的思路就欣喜若狂。本来学习就是这样，我们要好好享受由不会到会的这种快感，与人交流，相互学习，共同进步。

永做爱学习的小白，我是坏蛋哥，咱们下次再会。如果你也喜欢坏蛋哥的作品，记得👍加关注哦。