《动态规划》刷题训练

这篇具有很好参考价值的文章主要介绍了《动态规划》刷题训练。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

《动态规划》刷题训练,leetcode刷题,动态规划,算法

打家劫舍

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

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

题目解析

动态规划问题的特点:

  • 问题可以被划分为若干重叠子问题
  • 子问题可以通过已知的子问题求解,且子问题可以重复利用
  • 需要一个数据结构来存储子问题的解,以便在使用时取出

为什么这题能够使用动态规划?

  • 重叠子问题:
    设总共有 n n n家房屋,原问题则为有 n n n家房屋时所能偷窃到的最大金额。
    该问题能够划分为成若干重叠子问题:有 k ( k = 1 … … n − 1 ) k(k=1……n-1) k(k=1……n1)家房屋时能够偷窃到的最大金额
  • 子问题可以通过求解的子问题求解:
    k k k家房屋时,能够偷窃的最大金额:
    • k k k家不偷窃时,最大金额 = 当房屋为 k − 1 k-1 k1时,最大偷窃的金额
    • k k k家偷窃时,最大金额 = 第 k − 1 k-1 k1不偷窃时,最大金额 + 第 k k k家房屋能偷的钱= 当房屋为 k − 2 k-2 k2时,最大偷窃的金额 + 第 k k k家房屋能偷的钱

解题步骤:

  • 将原问题转化为一个或多个子问题
  • 定义问题的状态转移方程
  • 设置边界条件
  • 计算子问题的解并记录
  • 由子问题的解得到原问题的解
  • 问题【当有 k k k家房屋时,被偷窃最大的金额】可划分为(从左向右看):
    • k k k家不偷窃时,最大金额
    • k k k家偷窃时,最大金额
  • 状态转移方程:
    • 子问题为【第 k k k家不偷窃时,最大金额】:
      k k k家不偷窃,那么第 k k k家肯定不会构成相邻的非法条件。此时可以当第 k k k家不存在,所以问题变成:【房屋数量为 k − 1 k-1 k1时的最大偷窃金额】
    • 子问题为【第 k k k家偷窃时,最大金额】:
      此时第 k − 1 k-1 k1家肯定不能进行偷窃,否则会触发报警器。因此第 k − 1 k-1 k1家的状态只能是不偷窃,所以问题变成:【第 k k k家偷、第 k − 1 k-1 k1家不偷时,最大金额】
      状态转移方程:
      《动态规划》刷题训练,leetcode刷题,动态规划,算法

此时,我们定义一个二维数组 d p [ n ] [ 2 ] dp[n][2] dp[n][2]来存储子问题的解:

n n n表示一共有 n n n个重叠子问题

d p [ k ] [ 0 ] dp[k][0] dp[k][0]表示:房屋数量为 k k k时,且第 k + 1 k+1 k+1偷窃时最大的偷窃金额
d p [ k ] [ 1 ] dp[k][1] dp[k][1]表示:房屋数量为 k k k时,且第 k + 1 k+1 k+1家偷窃时最大的偷窃金额

设问题【当有 k k k家房屋时,最大得偷窃金额】表示为 f ( k ) f(k) f(k),根据上面的等式,此时 f ( k ) f(k) f(k)可表示成两个子问题:
f ( k ) = { f ( k − 1 ) k 不偷 n u m s ( k ) + d p [ k − 1 ] [ 0 ] k 偷 f(k)=\begin{cases} f(k-1) & k不偷 \\ nums(k) +dp[k-1][0] & k偷 \end{cases} f(k)={f(k1)nums(k)+dp[k1][0]k不偷k

f ( k − 1 ) f(k-1) f(k1)分别有 第 k − 1 k-1 k1家偷 和 第 k − 1 k-1 k1家不偷下对应的解,我们取最大即可:
f ( k − 1 ) = M A X { d p [ k − 1 ] [ 0 ] , d p [ k − 1 ] [ 1 ] } f(k-1)=MAX\{dp[k-1][0],dp[k-1][1]\} f(k1)=MAX{dp[k1][0],dp[k1][1]}

最终状态转移方程,可得:
f ( k ) = { M A X { d p [ k − 1 ] [ 0 ] , d p [ k − 1 ] [ 1 ] } k 不偷 n u m s ( k ) + d p [ k − 1 ] [ 0 ] k 偷 f(k)=\begin{cases} MAX\{dp[k-1][0],dp[k-1][1]\} & k不偷 \\ nums(k) +dp[k-1][0] & k偷 \end{cases} f(k)={MAX{dp[k1][0],dp[k1][1]}nums(k)+dp[k1][0]k不偷k

  • 边界条件,当 k = 0 k=0 k=0的时候,表示第 k + 1 = 1 k+1=1 k+1=1家的情况:
    • 1 1 1家=不=偷: d p [ 0 ] [ 0 ] = 0 dp[0][0]=0 dp[0][0]=0
    • 1 1 1家偷: d p [ 0 ] [ 1 ] = n u m s [ 0 ] dp[0][1]=nums[0] dp[0][1]=nums[0]

从状态转移方程看,我们需要从左到右的更新dp数组。

最后,附上Java实现方式:

class Solution {
    public int rob(int[] nums) {
    	//len表示有几家房子
        int len = nums.length;
		
		//定义dp数组存储子问题的解,原问题的解存储在dp[len-1]中
        int dp[][] = new int[len][2];
		
		//边界条件
        dp[0][0] = 0;//第一家不偷
        dp[0][1] = nums[0];//第一家偷

		//从左到右依次更新
        for(int i=1;i<len;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0]+nums[i];
        }
        return Math.max(dp[len-1][0],dp[len-1][1]);
    }
}

打家劫舍Ⅱ

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

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

题目解析

相比上面打家劫舍1.0版本,多了一个限制条件:首位相连

如何在上面的基础上考虑第一家和最后一家呢?

现在仅关注第一家:

  • 如果偷:第n家可不能偷
  • 如果不偷:第n家可偷可不偷

可以看到,当对第一家不偷时,那第一家可当作可有可无的,直接将第一家忽略,即只有第2~n家,转变成1.0版本形式

如果偷第一家,那么最后一家就不能偷,同理第n家可以被忽略

所以,可以分成两种情况:

  • 第一家偷:
    • 忽略第n家,对第1~(n-1)家执行1.0版本的算法
  • 第一家偷:
    • 忽略第1家,对第2~n家执行1.0版本的算法

最后,附上Java代码文章来源地址https://www.toymoban.com/news/detail-803430.html

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        
        //当家的数量等于1或者2的情况
        if(len==1)return nums[0];
        if(len<3)return Math.max(nums[0],nums[1]);
		
		//用于记录最大数额的变量
        int ans = 0;
		
		//记录子问题答案的数组
        int dp[][] = new int[len][2];
		
		//当第1家不偷,对1~len-1执行1.0的算法
		//忽略dp[0]  边界条件从1开始
        dp[1][0] = 0;dp[1][1] = nums[1];
        for(int i=2;i<len;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        //记录第1家不偷能获取的最大金额
        ans = Math.max(dp[len-1][0],dp[len-1][1]);
        
        //第1家偷,忽略最后一家,对0~len-2执行1.0的算法
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<len-1;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        //更新最大金额
        ans = Math.max(Math.max(dp[len-2][0],dp[len-2][1]),ans);
        return ans;
    }
}

到了这里,关于《动态规划》刷题训练的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】动态规划 刷题训练(六)

    点击查看:买卖股票的最佳时机 III 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入:p

    2024年02月11日
    浏览(29)
  • 【LeetCode】动态规划 刷题训练(二)

    点击查看:不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7 输出:28 示例

    2024年02月10日
    浏览(33)
  • 【LeetCode】动态规划 刷题训练(九)

    点击查看:467. 环绕字符串中唯一的子字符串 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串,所以 base 看起来是这样的: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”. 给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

    2024年02月15日
    浏览(36)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(56)
  • 【leetcode刷题之路】初级算法(2)——链表+树+排序和搜索+动态规划

    3.1 【链表】删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/ 给出的就是要删除的那个节点,直接前后移动就行了。 3.2 【双指针】删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 利用双指针left和right,首先让right遍历n个节点,再让两

    2024年02月10日
    浏览(49)
  • 《动态规划》刷题训练

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年01月19日
    浏览(44)
  • 算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    题目链接🔥🔥 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于

    2024年02月10日
    浏览(39)
  • Leetcode 刷题 动态规划

    309. 最佳买卖股票时机含冷冻期 1. 确定dp数组以及下标的含义 具体可以区分出如下四个状态: 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前就

    2024年02月11日
    浏览(45)
  • 【leetcode刷题之路】面试经典150题(8)——位运算+数学+一维动态规划+多维动态规划

    20 位运算 20.1 【位运算】二进制求和 题目地址:https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2envId=top-interview-150   按位逆序运算。 20.2 【位运算】颠倒二进制位 题目地址:https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2envId=top-interview-150   详见代码

    2024年04月16日
    浏览(73)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包