动态规划(三)

2020-10-10 本文已影响0人茶还是咖啡

House Robber

假设你是一个专业的小偷，打算洗劫一条街所有的房子，每个房子都有价值不同的宝物，但是如果你连续偷了两栋房子，就会触发报警系统，编程求出你最多可以偷窃价值多少的宝物
eg：
[3,4,1,2] -->6 [3,(4),1,(2)]
[4,3,1,2] -->6 [(4),3,1,(2)]

暴力解法

检查所有房子的组合，对每一个组合检查是否有相邻的房子，如果没有，记录其价值，找到最大值。
时间复杂度：O((2^n)*n)

递归树如下

状态转移方程

我们称对 ”考虑偷取[x...n-1]范围里的房子“ 的递归函数的定义，我们称之为"状态"

f(0)=max{ v(0)+f(2), v(1)+f(3), v(2)+f(4), ... v(n-3)+f(n-1), v(n-2), v(n-1) }

上面的函数f(x)代表从第x个房子偷取获取宝物的最大值，v(y)代表去除y号房子代表的价值。本题的是考虑从 "0号房子考虑，获取偷取宝物的最大值"，
即，

可以是偷取0号房子的宝物，加上从2号房子考虑偷取宝物的最大值；
可以是偷取1号房子的宝物，加上从3号房子考虑偷取宝物的最大值；
可以是偷取2号房子的宝物，加上从4号房子考虑偷取宝物的最大值；
...
可以是偷取n-3号房子的宝物，加上从n-1号房子考虑偷取宝物的最大值；
可以是偷取n-2号房子的宝物，加上从n号房子考虑偷取宝物的最大值，以为n号房子不存在，所以忽略。
可以是偷取n-1号房子的宝物...

这些方案中选择最大值即为本题的解。也就是上面的方程。该方程我们称之为"状态转移方程"。

递归函数

    /**
     * 获取宝物的最大值
     *
     * @param house 房子
     * @return 获取宝物的最大值
     */
    public int robs(int[] house) {
        return tryRobs(0, house);
    }

    /**
     * 尝试抢劫获取宝物的最大值
     *
     * @param index 开始考虑抢劫房子的编号
     * @param house 房子
     * @return 尝试抢劫获取宝物的最大值
     */
    private int tryRobs(int index, int[] house) {
        if (index >= house.length) {
            // 尝试抢劫房子的编号超出房子编号的最大值
            return 0;
        }
        // 用于记录本次抢劫房子的最大值
        int res = -1;
        for (int i = index; i < house.length; i++) {
            res = Integer.max(res, house[i] + tryRobs(i + 2, house));
        }
        return res;
    }

记忆化搜索

    /**
     * 获取宝物的最大值
     *
     * @param house 房子
     * @return 获取宝物的最大值
     */
    public int robs(int[] house) {
        int[] memo = new int[house.length];
        Arrays.fill(memo, -1);
        return tryRobsWithMemo(0, house, memo);
    }

    /**
     * 带记忆化搜索的尝试抢劫获取宝物的最大值
     *
     * @param index 开始考虑抢劫房子的编号
     * @param house 房子
     * @param memo  memo[x]开始考虑抢劫x号房子获取宝物的最大值
     * @return 尝试抢劫获取宝物的最大值
     */
    private int tryRobsWithMemo(int index, int[] house, int[] memo) {
        if (index >= house.length) {
            // 尝试抢劫房子的编号超出房子编号的最大值
            return 0;
        }
        if (memo[index] != -1) {
            return memo[index];
        }
        // 用于记录本次抢劫房子的最大值
        int res = -1;
        for (int i = index; i < house.length; i++) {
            res = Integer.max(res, house[i] + tryRobsWithMemo(i + 2, house,memo));
        }
        memo[index] = res;
        return res;
    }

动态规划

    int rob(int[] house) {
        int length = house.length;
        if (length == 0) {
            return 0;
        }
        int[] memo = new int[length];
        Arrays.fill(memo, -1);

        memo[length - 1] = house[length - 1];

        for (int i = length - 2; i >= 0; i--) {
            // 计算memo[i]的最大值
            for (int j = i; j < length; j++) {
                memo[i] = Integer.max(memo[i], house[j] + (j + 2 < length ? memo[j + 2] : 0));
            }
        }
        return memo[0];
    }

拓展

考虑偷取从[x...n-1]范围里的房子的宝物
考虑偷取从[0...x]范围里房子的宝物

House Robber II

和Hourse Robber 一样，不过这次实在环形的街道，也就是给定的数组中，第一个元素和最后一个元素为邻居，在不触碰警报的情况下能够窃取财产的最大值是多少？

House Robber |||

和House Robber 一样，不过这次是在一个小区中，整个小区呈二叉树的结构，在不触碰警报的前提下，能够窃取财产的最大值是多少？
eg:

             3                                                               3
            /  \                                                            / \
           2    3                                                          4   5
            \    \                                                        /  \  \
             3    1                                                      1    3  1
        最大值为3+3+1=7                                                 最大值为4+5=9

Best Time To Buy And Sell Stock with Cooldown

给定一个数组，表示一只股票在每一天的价格。设计一个交易算法，在这些天进行自动交易，要求：每天只能进行一次操作，在买完股票后，在下一天是不能购买的。问如何交易，能让利益最大化。
eg:
price=[1,2,3,0,2]
最佳交易方式：[buy, sell, colldown, buy, sell],利润为3，算法返回3