您现在的位置是:首页 > 正文

c++动态规划典型案例

2024-04-01 04:25:53阅读 6

动态规划

动态规划的三要素

重叠子问题、最优子结构、状态转移方程

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。

第⼆个凑零钱的问题,展⽰了如何流程化确定「状态转移⽅程」,只要通过
状态转移⽅程写出暴⼒递归解,剩下的也就是优化递归树,消除重叠⼦问题
⽽已。

计算机解决问题其实没有任何奇技淫巧,它唯⼀的解决办法就是穷举,穷举
所有可能性。算法设计⽆⾮就是先思考“如何穷举”,然后再追求“如何聪明
地穷举”。

动态规划的流程

具体来说,动态规划的一般流程就是三步:

暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法

就思考流程来说,就分为以下三步:

找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系

for 状态1 in 状态1的所有取值:
	for 状态2 in 状态2的所有取值:
		for ...
			dp[状态1][状态2][...] = 择优(选择1,选择2...)

常用的状态转移方程推导技巧

  • 数学归纳法

经典动态规划:高空扔鸡蛋🥚

我们选择在第 i 层楼扔了鸡蛋之后,可能出现两种情况:鸡蛋碎了,鸡蛋没碎。注意,这时候状态转移就来了:
如果鸡蛋碎了,那么鸡蛋的个数 K 应该减⼀,搜索的楼层区间应该从[1…N] 变为 [1…i-1] 共 i-1 层楼;
如果鸡蛋没碎,那么鸡蛋的个数 K 不变,搜索的楼层区间应该从 [1…N]变为 [i+1…N] 共 N-i 层楼。

经典动态规划:0-1背包问题👜

  • 问题描述

    给你⼀个可装载重量为 W 的背包和 N 个物品,每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i] ,价值为 val[i] ,现在让你⽤这个背包装物品,最多能装的价值是多少?

  • 明确状态

    【背包的容量】、【可选择的物品】

  • 明确选择

    【装进背包】 or 【不装进背包】

  • 明确dp数组的定义

    状态两个,因此首选二维数组

    👉👉dp[i][w]的定义如下:对于前i个物品,当前背包的容量为w,这种情况下可以装下的最大价值dp[i][w]

  • 确定base case

    根据对dp数组的定义,我们最终想求得的答案就是dp[N][W]。确定base case dp[0][...] = dp[...][0] = 0

    因为没有物品时或者背包没有空间时,能装下的最大价值就是0

  • 根据【选择】明确逻辑框架

    【装进背包】:如果把这第i个物品装入背包,那么dp[i][w]应等于dp[i-1][w-wt[i-1]] + val[i-1]

    即第i-1个物品留有wt[i-1]重量空间给第i个物品,由于从索引1开始,因此第i对应i-1

    【不装进背包】:如果不把这第i个物品装进背包,则继承之前的结果,那么最大价值dp[i][w] = dp[i-1][w]

    【综合考虑】:dp[i][w]等于【装进背包】和【不装进背包】两者带来最大价值的那个选择;
    d p [ i ] [ w ] = m a x ( d p [ i − 1 ] [ w ] , d p [ i − 1 ] [ w − w t [ i − 1 ] ] + v a l [ i − 1 ] ) dp[i][w] = max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1]) dp[i][w]=max(dp[i1][w],dp[i1][wwt[i1]]+val[i1])

  • 处理索引越界和边界情况

    if(w - wt[i-1] < 0)
    {
    	//这种情况下等同于不装入背包
    	dp[i][w] = dp[i-1][w];
    }
    
  • 迭代形式

    int knapsack(int W, int N, vector<int> &weight, vector<int> &value){
        vector<vector<int>> dp(N + 1, vector<int>(W + 1));
        //initialize base case
        for (int i = 0; i <= N; i++)
            dp[i][0] = 0;
        for (int j = 0; j <= W; j++)
            dp[0][j] = 0;
        //calculate dp
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= W; j++)
                if (j - weight[i - 1] < 0)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j - weight[i - 1]] + value[i - 1],
                                   dp[i - 1][j]);
        return dp[N][W];
    }
    

经典动态规划:完全背包问题👛

  • 问题描述

    给定不同面额的硬币和一个总金额,写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

    示例:输入:amount = 5,coins = [1 , 2 , 5]

    输出:4

    **解释:**有四种方式可以凑成总金额数5,2+2+1,2+1+1+1,1+1+1+1+1

  • 问题转换

    有⼀个钱包,最⼤金额为 amount ,有⼀系列硬币 coins ,每个硬币的金额为 coins[i] ,每个硬币的数量⽆限。请问有多少种⽅法,能够把钱包恰好装满?

    「完全背包问题」即指的是题中的硬币数量无限制。

  • 明确状态

    【钱包的容量】、【可选择的硬币】

  • 明确选择

    【装进钱包】 or 【不装进钱包】

  • 明确dp数组的定义

    状态两个,因此首选二维数组

    👉👉dp[i][j]的定义如下:只使用前i个硬币,当前钱包的容纳金额为j时,有dp[i][j]种方法能装满钱包!

    若只使⽤ coins 中的前 i 个硬币的⾯值,若想凑出⾦额 j ,有 dp[i][j] 种凑法。

  • 确定base case

    根据对dp数组的定义,我们最终想求得的答案就是dp[N][amount]。其中Ncoins数组的大小,

    确定base case: dp[0][...] = 0,dp[...][0] = 1

    因为没有硬币可以选择时,则无论如何都凑不出指定金额;如果指定金额为0,则空集是唯一解集。

  • 根据【选择】明确逻辑框架

    【装进钱包】:如果把这第i个硬币装入钱包,那么dp[i][j]应等于dp[i-1][j-coins[i-1]]

    即第i-1个物品留有wt[i-1]重量空间给第i个物品,由于从索引1开始,因此第i对应i-1

    【不装进背包】:如果不把这第i个硬币装进背包,则继承之前的结果,那么方法数dp[i][w] = dp[i-1][w]

    【综合考虑】:dp[i][w]等于【装进背包】和【不装进背包】两个选择方法数之和
    d p [ i ] [ w ] = d p [ i − 1 ] [ j ]   +   d p [ i ] [ j − c o i n s [ i − 1 ] ] dp[i][w] = dp[i-1][j]~+~dp[i][j-coins[i-1]] dp[i][w]=dp[i1][j] + dp[i][jcoins[i1]]

  • 处理索引越界和边界情况

    if(j - coins[i-1] < 0)
    {
    	//这种情况下等同于不装入背包
    	dp[i][j] = dp[i-1][j];
    }
    
  • 迭代形式

    int change(int amount, vector<int> &coins){
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        //initialize base case
        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;
        for (int j = 1; j <= amount; j++)
            dp[0][j] = 0;
        //dp begin
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= amount; j++)
                if (j - coins[i - 1] < 0)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
        return dp[n][amount];
    }
    

经典动态规划:子集背包问题💼

  • 问题描述

    给定一个只包含正整数和非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

  • 问题转换

    那么对于这个问题,我们可以先对集合求和,得出 sum把问题转化为背包问题:

    ​ 给⼀个可装载重量为 sum / 2 的背包和 N 个物品,每个物品的重量为nums[i] 。现在让你装物品,是否存在⼀种装法,能够恰好将背包装满?

  • 明确状态

    【容量为数组元素和/2】、【可选择的数组元素】

  • 明确选择

    【装进数组】 or 【不装进数组】

  • 明确dp数组的定义

    状态两个,因此首选二维数组

    👉👉dp[i][w]的定义如下:对于前i个数组元素,当前背包的容量为w,若dp[i][w]true则说明恰好可以将背包装满,若dp[i][w]false,则说明不能恰好把背包装满。

  • 确定base case

    根据对dp数组的定义,我们最终想求得的答案就是dp[N][W]。确定base case dp[0][...] = false,dp[...][0] = true

    解释:当没有物品可选择的时候,则装不满背包;当背包容量为0的时候,则已经装满了背包。

  • 根据【选择】明确逻辑框架

    【装进背包】:如果把这第i个物品装入背包,那么dp[i][w]应等于dp[i-1][w-nums[i-1]]

    即第i-1个物品留有nums[i-1]重量空间给第i个物品,由于从索引1开始,因此第i对应i-1

    【不装进背包】:如果不把这第i个物品装进背包,则继承之前的结果,那么最大价值dp[i][w] = dp[i-1][w]

    【综合考虑】:dp[i][w]等于【装进背包】和【不装进背包】两者谁带来最大利益,即取逻辑或的关系;
    d p [ i ] [ w ]   =   d p [ i − 1 ] [ w − n u m s [ i − 1 ] ]    ∣ ∣    d p [ i − 1 ] [ w ] dp[i][w]~=~dp[i-1][w-nums[i-1]] ~~||~~ dp[i-1][w] dp[i][w] = dp[i1][wnums[i1]]    dp[i1][w]

  • 处理索引越界和边界情况

    if(w - nums[i-1] < 0)
    {
    	//这种情况下等同于不装入背包
    	dp[i][w] = dp[i-1][w];
    }
    
  • 迭代形式

    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        for (const auto &i : nums) sum += i;
        if (sum % 2 == 1) return false;
        int target = sum / 2; //背包问题中的总重量
        int n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1));
        //initialize base case
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= target; j++)
                if (j - nums[i - 1] < 0)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] ||
                               dp[i - 1][j];
        return dp[n][target];
    }
    

经典动态规划:编辑距离🏳

  • 问题描述

    给定两个字符串s1s2,计算出将s1转换成s2所使用的最少操作数。你可以对字符串进行如下三种操作:

    1.插入一个字符

    2.删除一个字符

    3.替换一个字符

    示例:输入:s1 = "horse,"s2="ros"

    输出:3

  • 明确状态

    s1子串长】、【s2子串长】

  • 明确选择

    【跳过(skip)】 、【删除(delete)】、【插入(insert)】、【替换(replace)】

  • 明确dp数组的定义

    状态两个,因此首选二维数组。解决两个字符串的动态规划问题,⼀般都是⽤两个指针i,j分别指向两个字符串的最后,然后⼀步步往前⾛,缩⼩问题的规模。

    👉👉dp[i][j]的定义如下:对于s1的前i个字符与s2的前i个字符,其最小操作数为dp[i][j]

  • 确定base case

    根据对dp数组的定义,我们最终想求得的答案就是dp[s1.len][s2.len]。确定base case dp[0][...] = [...],dp[...][0] = [...]

    解释:s1空与s2的前n个做匹配,需进行n次插入操作;s2空与s1的前m个做匹配,需进行m次插入操作。

  • 根据【选择】明确逻辑框架

    如果两个字符相同:

    【跳过(skip)】:dp[i][j] = dp[i-1][j-1]

    如果两个字符不同:

    【删除(delete)】:dp[i][j] = dp[i-1][j] + 1

    【插入(insert)】:dp[i][j] = dp[i][j-1] + 1

    【替换(replace)】:dp[i][j] = dp[i-1][j-1] + 1

    【综合考虑】:

    字符相同的情况:
    d p

网站文章

  • 单向链表的实现--查询

    单向链表的实现--查询

    前一讲讲到的链表创建和插入,这里我们直接使用前面的程序功能来辅助实现链表的数据查询。 功能:根据指定的 ISBN 或书名查找相应图书的有关信息, 并返回该图书在表中的位置序号。 singLinkList.h头文件内容声明和定义:...............

    2024-04-01 04:25:46
  • python乒乓球比赛规则_使用Python进行体育竞技分析(预测球队成绩)

    python乒乓球比赛规则_使用Python进行体育竞技分析(预测球队成绩)

    今天我们用python进行体育竞技分析,预测球队成绩一. 体育竞技分析的IPO模式 :输入I(input):两个球员的能力值,模拟比赛的次数(其中,运动员的能力值,可以通过发球方赢得本回合的概率来表示...

    2024-04-01 04:24:58
  • java怎么添加作者信息_Eclipse新建类的时候如何自动添加注释(作者,时间的信息...

    java怎么添加作者信息_Eclipse新建类的时候如何自动添加注释(作者,时间的信息...

    方法一:Eclipse中设置在创建新类时自动生成注释windows–&gt;preferenceJava–&gt;Code Style–&gt;Code Templatescode–&gt;new J...

    2024-04-01 04:24:49
  • 一年时间,拿到了人生中的第一个10万

    一年时间,拿到了人生中的第一个10万

    目录一、努力创造奇迹,请相信,你的付出终将会有所收获1、努力是必要条件2、成功需要一个拐点,而它就是哪吒成功的拐点三、收获了90000的粉丝四、写博客居然还可以赚钱?1、周榜2、曾几何时,嗨,成了日常...

    2024-04-01 04:24:42
  • C# PictureBox——SizeMode属性 最新发布

    c#、picturebox

    2024-04-01 04:24:01
  • Quic_Wire_layout_specification_翻译

    英文原文链接:QUIC wire specificationQUIC概述  本节我们主要介绍QUIC的关键功能和优点。QUIC功能上等于TCP+TLS+HTTP/2,但是基于UDP传输的。QUIC优于TCP+TLS+HTTP/2的关键点有:connect连接建立的低延时灵活的拥塞控制无头部阻塞的多路复用(TCP是有头部阻塞的)对头部和负载进行认证和加密流和连接的流控连接迁移c...

    2024-04-01 04:23:54
  • 【Xcode】Swift代码自动格式化--SwiftFormat安装与使用

    【Xcode】Swift代码自动格式化--SwiftFormat安装与使用

    已测试没问题的文章:

    2024-04-01 04:23:41
  • HttpWatch工具简介及使用技巧

    HttpWatch工具简介及使用技巧

    一 概述:HttpWatch强大的网页数据分析工具.集成在Internet Explorer工具栏.包括网页摘要.Cookies管理.缓存管理.消息头发送/接受.字符查询.POST数据和目录管理功能.报告输出 HttpWatch是一款能够收集并显示页页深层信息的软件。它不用代理服务器或一些复杂的网络监控工具,就能够在显示网页同时显示网页请求和回应的日志信息。甚至可以显示浏览器缓存和IE

    2024-04-01 04:22:57
  • js识别android ios9,JS判断客户端是IOS还是ANDROID

    // 1. 定义终端判断对象let browser = {versions: function () {let u = navigator.userAgent,app = navigator.appVersion;return {trident: u.indexOf('Trident') > -1, //IE内核presto: u.indexOf('Presto') > -1, //o...

    2024-04-01 04:22:50
  • ERROR: Couldn&#39;t find any revision to build.【Jenkins】

    ERROR: Couldn&#39;t find any revision to build.【Jenkins】

    2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

    2024-04-01 04:22:01