多状态动态规划之删除并获得点数

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

1. 题目分析

题目链接选自力扣 : 删除并获得点数
image.png
结合示例 1 来分析 : 由于它不是有序的, 对于我们理解实例有点不太方便, 因此我们将示例 1 排序后在来看
image.png
image.png
也就是说, 选择那个节点删除后就获得这个值对应节点数. 同时这个节点的值相邻的值不能选

2. 状态表示

这时候用用动态规划来解还是一头雾水中, 怎么就能和动态规划联系上了呢 ?

先来看这样一组示例 : 1 2 3 4 5
image.png
当我们把 1 选上后, 相邻值的 2 就要被删掉. 因此它下一个位置只能在 3 开始往后, 例如下面这样
image.png
这时候这个问题就变成了 当选中 1 以后, 相邻的不能选, 选择后面 3 ~ 5 位置的最大节点数加上 1 位置的节点数.即为最终的最大节点数.

这时候惊人的发现, 有没有很像我们的 " 打家劫舍(详细链接) " 问题 ? 相邻两个数不能偷窃, 从任意一个位置开始到结束时的最大偷窃金额.

虽然它非常接近我们的 " 打家劫舍 " , 但是此处我们的数组之间的数值不一定是连续的. 例如 : 1 1 2 2 4 4 6

此时在带入到 " 打家劫舍(详细链接) " 问题时就不合适了. 偷了 1 位置则不能偷 2 位置, 可以从 3 位置开始偷, 但这不符合我们题目的要求
image.png
这是按照 " 打家劫舍(详细链接) " 问题的思路来偷窃的. 显然是不行的, 因为题目要求选了 1 以后, 相邻数值的节点数 2 和 0 都要被删除, 应该为这样
image.png
因此, 为了解决这种情况, 我们需要将这个数组给它进行预处理, 让它变成可以使用 " 打家劫舍(详细链接) " 问题来解决的数组形式, 即:利用下标连续来对应 " 打家劫舍 " 问题的连续数组 !
image.png
创建一个数组来存储统计原数组中的相同的值. 0 下标处就统计原数组中有多少个 0, 1 下标处就统计原数组中有多少个 1, 2 下标处就统计原数组中有多少个 2 … 以此类推. 最终根据下标的连续性来进行 " 打家劫舍(详细链接) " 问题的处理.
处理后的数组我们来演示一下 :
image.png当选择所有 1 节点数后, 所有的节点值为 0 和 2 的都要被删除. 此时选择两个 1 节点获得 2 点节点数. 下一次只能选从 4 位置开始.

在看我们的处理后的数组. 偷窃 1 号房间后, 2 号房间就不能偷了, 那么只能从 3 号房间开始偷. 但是 3 号房间不存在. 因此只能从 4 号房间开始偷. 最终的最多盗窃金额就为 nums[1] + [4-n-1] 区间内的最多盗窃金额. 就可以对应上我们的 " 打家劫舍(详细链接) " 问题了.

3. 状态转移方程

既然是一个 " 打家劫舍 " 问题. 那么就来回顾一下它的状态转移方程. 下面的盗窃金额即为题目的最大节点数 !

以 i 位置为结尾, 从任意位置开始偷窃到 i 位置时的最大盗窃金额. 即 dp[i]. 偷窃到 i 位置时, 我们还可以细分为两个状态, 也就是偷窃 i 位置的 array[i] 和 不偷窃 i 位置的 array[i]

  1. 偷窃到 i 位置时, 偷窃 array[i]

这种情况我们表示为 f[i]. 即从某一位置开始偷窃到 i 位置时, 并偷窃 array[i]

  1. 偷窃到 i 位置时, 不偷窃 array[i]

这种情况我们表示为 g[i]. 即从某一个位置开始偷窃到 i 位置时, 不偷窃 array[i]

来推导一下这两种情况下的状态转移方程.

  1. 偷窃到 i 位置时, 偷窃 array[i]

image.png
偷窃到 i 位置后, 选择偷窃 array[i], 那么此时 i - 1 位置是必定不能偷的. 因此最大的偷窃金额就为从任意位置起始到 i - 1 位置并且 array[i-1] 位置不偷窃. 对应到我们的状态表示则为 g[i-1], 最后在加上必偷的 array[i].

最终最大的偷窃金额为, 即状态转移方程:f[i] = g[i-1] + array[i]

  1. 偷窃到 i 位置时, 不偷窃 array[i]

image.png
这种情况下, 偷窃到 i 位置时, array[i] 不偷窃, 那么 i - 1 位置就有两种情况可以选

  1. i-1 位置偷窃 array[i-1]

image.png
这个情况下, 也就是从起始位置偷窃到 i - 1 位置, 并且偷窃 array[i-1] 正好对应到我们的状态表示中的 f[i-1]. 最大的盗窃金额即为 f[i-1]

  1. i-1 位置不偷窃 array[i-1]

image.png
偷窃到 i -1 位置时, 不偷窃 array[i-1], 正好对应我们的状态表示中的 g[i-1]. 最大盗窃金额即为 f[i-1]

第二种情况的状态转移方程是有两种细分的情况组成的. 最终这种情况下的最大偷窃金额为两种情况的最大值, 即状态转移方程 : g[i] = Math.max(f[i-1], g[i-1])

4. 初始化

根据两种不同转态的状态转移方程 f[i] = g[i-1] + array[i] 和 g[i] = Math.max(f[i-1], g[i-1]) 知道, 填写 g[0] 和 f[0] 时会发生越界错误. 因此这两个位置需要进行初始化.

经过分析, 当只有一个元素时, 此时有两种偷窃情况.

  1. 偷窃这个位置的 array[0], 最终的偷窃金额为 f[0] = array[0]
  2. 不偷窃这个位置的 array[0], 最终的偷窃金额为 g[0] = 0

5. 填表顺序

根据状态转移方程, 想要填写 i 位置的值, 就必须先知道前一个位置的值. 因此填表的顺序为从左往右

6. 返回值

题目要求从某一位置开始到数组末尾 n-1 位置结束时存储的最大盗窃金额. 由于存在两种状态, 因此对这两种状态的结尾值取最大值返回. Math.max(f[n-1], g[n-1])文章来源地址https://www.toymoban.com/news/detail-509360.html

7. 代码演示

class Solution {
    public int deleteAndEarn(int[] nums) {

        // 1. 创建 dp 表
        int n = 10001; // 和预处理的数组一样大, 下标直接对应不需要考虑映射关系

        int[] f = new int[n]; // 从任意位置删除到 i 位置时, 选择 nums[i]时所获得的最大节点数
        int[] g = new int[n]; // 从任意位置删除到 i 位置时, 不选择 nums[i]所获得的最大节点数
        
        // 预处理 nums 数组让其下标连续对应 "打家劫舍" 问题
        int[] array = new int[n]; // 根据题目开辟足够大的空间存储
        for(int x : nums) {
            array[x] += x; 
        }

        // 2. 初始化
        f[0] = array[0];

        // 3. 填写 dp 表
        for(int i = 1; i < n; i++) {
            // 根据不同的状态转移方程填写
            f[i] =  g[i-1] + array[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }

        // 4. 确认返回值
        return Math.max(f[n-1], g[n-1]);
    }
}

到了这里,关于多状态动态规划之删除并获得点数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • (动态规划) 剑指 Offer 60. n个骰子的点数 ——【Leetcode每日一题】

    难度:中等 把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s 。输入 n ,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1 输出: [0.16667,0.16667,0.16667,

    2024年02月11日
    浏览(45)
  • 【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 剑指 Offer 60. n个骰子的点

    2023年04月19日
    浏览(59)
  • 【算法】——动态规划题目讲解

    本期继续为大家带来的是关于动态规划类题目的讲解,对于这类题目大家一定要多加练习,争取掌握。 链接如下: 62. 不同路径 题目如下: 算法思路: 1. 状态表⽰:  对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式: i. 从 [i, j] 位置出发; ii. 从起始位置出发

    2024年02月10日
    浏览(42)
  • 动态规划2:题目

    目录 第1题 Fibonacci 第2题 字符串分割(Word Break) .第3题 三角矩阵(Triangle) 第4题 路径总数(Unique Paths) 第5题 最小路径和(Minimum Path Sum) 第6题 背包问题 第7题 回文串分割(Palindrome Partitioning) 第8题 编辑距离(Edit Distance) 第9题 不同子序列(Distinct Subsequences) 分析问题: 1. 状态定义F(i):第

    2024年02月06日
    浏览(43)
  • 动态规划题目练习

    动态规划背包问题-CSDN博客 动态规划基础概念-CSDN博客 题目描述 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河

    2024年04月25日
    浏览(37)
  • 【LeetCode】动态规划类题目详解

    所有题目均来自于LeetCode,刷题代码使用的Python3版本 如果某一个问题有重叠的子问题,则使用动态规划进行求解是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的,这一点区别于贪心算法 动态规划五部曲 确定dp数组以及下标的含义 确定递推公式 dp数组如何

    2024年04月11日
    浏览(49)
  • 代码随想录 动态规划-基础题目

    目录 509.斐波那契数  70.爬楼梯 746.使用最小花费爬楼梯 62.不同路径 63.不同路径|| 343.整数拆分 96.不同的二叉树 509. 斐波那契数 简单 斐波那契数  (通常用  F(n)  表示)形成的序列称为  斐波那契数列  。该数列由  0  和  1  开始,后面的每一项数字都是前面两项数字的和

    2024年03月18日
    浏览(77)
  • 一维动态规划经典力扣题目(一)

    目录 题一:斐波那契数列 题目二:最低票价 题三:解码方法 递归方法是2的n次方的时间复杂度。 递归代码: 带有缓存的递归,会使时间复杂度得到大幅度优化。 时间复杂度为O(n)。 缓存即记录中间值         优化的方法:         代码:         代码:

    2024年02月21日
    浏览(42)
  • C++算法之动态规划(ACWING题目)

    动态规划时间复杂度:状态数量*转移计算量 线性DP 一.数字三角形 动态规划:     1.状态表示:         集合:f[i, j]表示所有从起点走到(i, j)的路径         属性:所有路径上的数字之和的最大值     2.状态计算:         如何得到f[i, j]?             从左边路径走到和

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

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

    2024年02月09日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包