重拾C++之菜鸟刷算法第16篇 --- 动态规划(总结篇)

2024-03-30 23:28

本文主要是介绍重拾C++之菜鸟刷算法第16篇 --- 动态规划(总结篇),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划

五部曲

  1. 确定dp数组的含义
  2. 递推公式
  3. 正确进行初始化
  4. 遍历顺序
  5. 举例推到dp数组

01 背包问题

第一种:填满背包所需的最大价值

有n件物品和一个最多可以背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i],所有物品只能使用一次。

滚动数组解法

  1. 首先确定dp数组含义:dp[j] 表示 容量为 j 的背包能背的最大价值是 dp[j]

  2. 确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    只有两种情况

    • 第一种是当物品i的重量大于背包j的重量,物品i无法放入背包,因此背包的价值依然和前面相同
    • 第二种是因为dp[j - weight[i]]表示 j - weight[i] 重量的时候,此时最大的价值,那么dp[j - weight[i]] + value[i] 表示此时的背包放入物品i得到的最大价值
  3. 初始化:背包容量为0的话,其价值也为0,因此dp[i] = 0

  4. 遍历顺序:先遍历物品数量,再从背包容量倒序遍历,防止物品重复使用

  5. 举例说明dp数组

416. 分割等和子集 - 力扣(LeetCode)

1049. 最后一块石头的重量 II - 力扣(LeetCode)

第二种:装满容量为x的背包,有几种方法

  1. 首先确定dp数组含义:dp[j] 表示 容量为 j 的背包有 dp[j] 种方法

  2. 确定递推公式:dp[j] += dp[j - weight[i]] (组合类问题)

  3. 初始化:背包容量为0的话,其价值也为0,因此dp[i] = 0

  4. 遍历顺序:先遍历物品数量,再从背包容量倒序遍历,防止物品重复使用

  5. 举例说明dp数组

494. 目标和 - 力扣(LeetCode)

474. 一和零 - 力扣(LeetCode)

完全背包

与01背包唯一不同的地方是,每种物品有无限件

  1. 首先确定dp数组含义:dp[j] 表示 容量为 j 的背包能背的最大价值是 dp[j]

  2. 确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    只有两种情况

    • 第一种是当物品i的重量大于背包j的重量,物品i无法放入背包,因此背包的价值依然和前面相同
    • 第二种是因为dp[j - weight[i]]表示 j - weight[i] 重量的时候,此时最大的价值,那么dp[j - weight[i]] + value[i] 表示此时的背包放入物品i得到的最大价值
  3. 初始化:背包容量为0的话,其价值也为0,因此dp[i] = 0

  4. 遍历顺序:先遍历物品数量,再从小到大遍历背包容量(i那位完全背包的物品是可以添加多次的)

  5. 举例说明dp数组

518. 零钱兑换 II - 力扣(LeetCode)

377. 组合总和 Ⅳ - 力扣(LeetCode)

这篇关于重拾C++之菜鸟刷算法第16篇 --- 动态规划(总结篇)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862860

相关文章

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat