0.动态规划问题

一.打家劫舍

0.动态规划问题

动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题,进行解决，从而一步步获取最优解的处理算法

动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用

对于动态规划问题,大致可以分为以下几步:

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

一.打家劫舍

1.题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

力扣:力扣

2.问题分析

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

根据题目的意思,可以设一维数组dp[i],它的含义为:当小偷偷到第i家的时候,可以偷到的最高金额为dp[i].

2.确定递推公式

小偷偷窃到第i家的时候,有两种选择,一种可以选择偷窃第i家,一种可以选择不偷窃第i家

当不偷窃第i家的时候,dp[i]=dp[i-1],这里表示偷窃到第i-1家可以偷窃的最大金额, 可以由前一次推测出来,但这里并不是表示前一家一定偷窃

当偷窃第i家的时候, 由题意表示:不能连续偷窃相邻的两家,否则会发出警报,此时说明第i-1家是一定不可以偷窃的,因此需要得到偷窃到i-2家可以偷窃的最大金额加上偷窃到的第i家的金额,所以dp[i]=dp[i-2]+nums[i]

因此最终的答案就是两者的最大值递推公式为:dp[i]=max(dp[i-1],dp[i-2]+nums[i])

            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

3.dp数组如何初始化

根据递推公式可以看出,至少需要求出dp[0]和dp[1]的公式才可以进行之后的递推,具体的代码如下

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

4.确定遍历顺序

由递推公式可以看出,dp[i]=max(dp[i-1],dp[i-2]+nums[i]),可以看出dp[i]的推导需要前面的dp数组元素的支撑,所以要进行从前到后的递推推导

5.举例推导dp数组

对于[1,2,3,1]进行填表处理

i	0	1	2	3
dp[i]	1	2	4	4

3.代码实现

    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];


    }

二.打家劫舍 II

1.题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

力扣:力扣

2.问题分析

此题与上一题基本相似,主要的一处不同就是这一题的房子是首位联通的,说明如果你选择了第一个房间,就不能选择最后房间了.

所以我们需要考虑的就是能否把这一题转换为和上一题一样来做这一题,我们可以这样来做

情况一:只考虑首元素和不包含尾元素的数组元素

情况二:只考虑尾元素和不包含首元素的数组元素

两种情况分别求出来,取两者最大值就是要求的答案了,因为第一种情况相当于可选(不一定选)首元素,不选尾元素,而第二种请款相当于可选(不一定选)尾元素,不选首元素,这两种情况就包含了几步选首元素,也不选尾元素的情况

这样之后就可以转换为第一个问题了,只需要添加了一个选择的范围就好了

5.举例推导dp数组

对dp数组进行填表的操作

i	0	1	2	3
dp1[i]	1(start)	2	4(end)	0
dp2[i]	0	2(start)	3	3(end)

3.代码实现

    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);
        return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));

    }

    public int robRange(int[] nums, int start, int end) {//左闭右闭
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[end];
    }

三.打家劫舍 III

1.题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

力扣:力扣

2.问题分析

这道题目算是树形dp的入门题目，因为是在树上进行状态转移，需要我们使用递归三部曲加上动规五部曲进行结题

因为是树形的结构,所以我们首先确定的是哪种遍历顺序:主要有深度优先遍历(前中后序),广度优先遍历,本题需要采用后序遍历,因为需要逐层递归上到最终的根结点,确定最终的结果

接下来拿这个树举例

递归三部曲加上动规五部曲:

1.确定递归函数的参数和返回值

这个时候每个结点和上边两题一样,只有两种状态,偷或者不偷,所以dp数组就两个状态,偷与不偷所获得的金额,下标为0记录的是不偷该节点所获得的最大金额,下标为1记录的是偷该节点所获得的最大金额,所以返回值为int[]的数组,函数为:

    public int[] robAction1(TreeNode root) {

    }

2.确定终止条件

当遍历的过程中遇到空节点的时候,自然结束终止,这个时候dp[0]=0,dp[1]=0,相当于个dp数组进行了初始化

        if (root == null)
            return res;

3.确定遍历顺序

我们已经确定了采用后序遍历的方式,这样才能一层一层的递归到根结点,进行最大金额的统计

遍历完左节点,得到偷与不偷的最大金额

遍历完右节点,得到偷与不偷的最大金额

        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);

4.确定单层递归的逻辑

由题意可知:偷当前结点,就不可以偷他的孩子结点,不偷当前结点,就可以

所有就两种情况:偷当前结点:dp[1]=root.val+left[0]+right[0]

不偷当前结点:dp[0]=max(left[0],left[1])+max(right[0],right[0])

        // 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
        dp[1] = root.val + left[0] + right[0];

5.举例推导dp数组

对dp数组进行填表的操作

3.代码实现

public class Rob3 {


    public int rob(TreeNode root) {
        int[] ints = robAction1(root);
        return Math.max(ints[0], ints[1]);


    }
    //dp数组含义:下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
    public int[] robAction1(TreeNode root) {
        int dp[] = new int[2];
        if (root == null)
            return dp;

        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);
        // 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
        dp[1] = root.val + left[0] + right[0];
        return dp;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

四.打家劫舍 IV

1.题目描述

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数数组 k ，表示窃贼将会窃取的最少房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的最小窃取能力。

力扣:力扣

2.问题分析

看到这个题目的时候,看到「最大化最小值」或者「最小化最大值」就要想到二分答案

二分的范围是什么呢?最大值肯定是数组元素的最大值,最小值是从0开始(不是数组元素最小值,因为可能出现k=0的情况).

二分一大必须条件是必须要有单调性,因此这个时候我们发现当窃取能力比较大的时候,这个时候可以窃取的房子的数量也是相应比较多的,肯定可以满足窃取k个房子的条件,但是窃取能力比较小的时候,可能无法窃取房子数量达到k个,因此不满足题意,所以窃取能力和k值是存在单调的.

接下来就需要判断窃取的最大房子数是否可以达到k个房子的条件,这个时候就需要动态规划解决问题了.

还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

dp[i]的含义:当窃取到第i个房子的时候,能够窃取的最大房子数为dp[i]个

2.确定递推公式

对于第i个房子,如果当前房子的金额小于等于窃取能力,有两种状态,窃取和不窃取(注意:不能窃取相邻的房子)

当不窃取时:dp[i]=dp[i-1];

当窃取时:dp[i]=dp[i-2]+1;

所以取最大值 dp[i]=max(dp[i-1],dp[i-2]+1)

如果当前房子的金额大于窃取能力,表示当前房子不可以窃取,因此dp[i]=dp[i-1]

            if (nums[i] <= mx) {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + 1);
            } else {
                dp[i] = dp[i - 1];
            }

3.dp数组如何初始化

由递推公式可以看出,dp[i]是由前面两项递推出来的,因此至少要对dp[0]和dp[1]进行初始化

当nums[0]<=mx的时候,当前房子是可以窃取的,dp[0]=1,否则dp[0]=0;

当nums[0] <= mx || nums[1] <= mx的时候,表示任其一个房子可以进行窃取dp[1]=1,如果两者都大于mx,表示dp[1]=0

        if (nums[0] <= mx)
            dp[0] = 1;
        if (nums[0] <= mx || nums[1] <= mx)
            dp[1] = 1;

4.确定遍历顺序

由递推公式可以看出,dp[i]=max(dp[i-1],dp[i-2]+1),可以看出dp[i]的推导需要前面的dp数组元素的支撑,所以要进行从前到后的递推推导

5.举例推导dp数组

不同的mx对应不同的dp数组,过多省略推导.

3.代码实现

    //打家劫舍 IV  二分
    public int minCapability(int[] nums, int k) {
        if (nums.length == 1)
            return nums[0];
        int max = 0;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        //手写二分
        int left = 0, right = max;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(nums, k, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return check(nums, k, left) ? left : left + 1;


    }

    /**
     * 当窃取的最大金额为mx,能窃取的最大房屋数是否可以大于等于k
     *
     * @param nums
     * @param k
     * @param mx
     * @return
     */
    public boolean check(int[] nums, int k, int mx) {
        int[] dp = new int[nums.length];
        if (nums[0] <= mx)
            dp[0] = 1;
        if (nums[0] <= mx || nums[1] <= mx)
            dp[1] = 1;
        for (int i = 2; i < nums.length; ++i) {
            if (nums[i] <= mx) {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + 1);
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[nums.length - 1] >= k;


    }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101053.html