简单暴力到dp的优化（入门篇）

淡淡的烟草味﹌ 2022-05-27 09:55 157阅读 0赞

**上篇，我们提到，遇到问题，首先根据定义写出笨方法，找出依赖关系（有些题这一步就不太简单，要自己归纳关系），然后进行优化，下面，我们通过几道此方面的经典的，较为简单的二维题目进行讲解。**

**开始根据题来说明：**

# ***第一个萌新题*** #

**给定数组arr, arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张， 再给定一个整数aim 代表要找的钱数，求组成aim 的最少货币数。**

**\[举例\]**

**arr=\[5,2,3\], aim=20。**

**4 张5 元可以组成20 元，其他的找钱方案都要使用更多张的货币，返回4。**

**arr=\[5,2,3\], aim=0。**

**不用任何货币就可以组成0 元，返回0。**

**arr=\[3,5\],aim=2。**

**根本无法组成2 元，钱不能找开的情况下默认返回-1。**

**(你要是想贪心就贪吧，反正我不贪)**

**定义f(a,b)代表的是a面值及之前的货币，组成b元的最少张数。那f(arr\[-1\],aim)就是我们想求的答案。现在分析，怎样通过前面的状态推出结果？对于货币arr\[-1\]，我们可以一张都不用，那最少张数其实就是f(arr\[-2\],aim)，我们也可以用一张arr\[-1\]，最少张数就可能是f(arr\[-2\],aim-arr\[-1\])+1（用之前的钱组成aim-arr\[-1\]元钱，然后加一张arr\[-1\]），同理，我们可以用两张arr\[-1\]，或者更多，直到下一个就超过aim的时候。所以我们应该在所有情况中选最小的，**

**归纳表达式：**

**f(a,b)=min(f(arr\[a-1\],b-k\*arr\[a\])+k),k>=0,且b-k\*arr\[a\]>=0**

**当然，以前也提到过，直接递归我们会有大量重复计算，所以需要记下来之前的结果供我们使用。有两个参数代表现在的状态，所以生成二维表。**

**l=\[\[0 for i in range(len(arr))\] for i in range(aim+1)\]\#**

**我们看，f(arr\[a\],b)和谁有关？和上一行，也就是arr\[a-1\]那一行的很多左边元素有关。**

**所以确定打表顺序，从上到下，从左到右，打表，一个一个打，l\[a\]\[b\]=min(f(a-1,b-k\*arr\[a\])+k),依次推出l\[a\]\[b\]，右下角就是答案。**

**但是，还是有相当多的重复计算，我们的l\[a\]\[b-arr\[a\]\]其实就是根据除了l\[a-1\]\[b\]的左边那些元素求的的最小值**

**所以l\[a\]\[b\]=min(l\[a\]\[b-arr\[a\]\]+1,l\[a-1\]\[b\]）。**

其实和左边和上边元素相关的背包，还有一些别的题，都是如此。对于本物品，当前决策就是拿或不拿，以前的最优情况

**l\[a\]\[b-arr\[a\]\]**和**l\[a-1\]\[b\]**已经有了。不用管的。结合当前状态的定义，就明白了。

**至此，时间优化到严格o(a\*b),空间o(a\*b)，空间还能优化到o(min(a,b))，下一个题讲压缩方法。**

# ***第二个萌新题*** #

**给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最小路径和。**

**1 3 5 9**

**8 1 3 4**

**5 0 6 1**

**8 8 4 0**

**路径：1 3 1 0 6 1 0路径和最小，返回12**

**生成和矩阵相同大小的二维表DP，用来记录当前的最小路径和**

**（以后也不分析暴力的时间复杂度了）**

**对于普遍的位置i，j，只有i-1,j和i,j-1这两个位置可以一步走到这里，所以**

**DP\[i,j\]=min(DP\[i,j-1\],DP\[i-1,j\]）+L\[i,j\]**

**压缩：我们发现，除了这个位置上本身的数，DP\[i,j\]只和DP表中左边和上边的值有关，所以可以生成长度为矩阵较小边长一维表，用两层循环。注意顺序，从左向右打表，只有这样，左边的那个元素才是被更新过的，才是本行的左边那个元素。**

**最左边的DP值是直接累加的，其他位置**

**For i 0 to 高度:**

**For j 0 to 宽度**

**DP\[j\]=min(DP\[j-1\],DP\[j\]）+L\[i,j\]**

**时间不变，空间优化到o(较小边长）**

# ***第三道萌新题*** #

***题干和第一题一样，请返回所有的还钱方法有多少种***

**经过一二题，应该自己会做了。**

**（请记住：一般问方法的题目，只需把式子中max或者min改为sum即可）**

n=int(input())
    dp=[0]*(n+1)
    dp[0]=1
    tmp=[1,5,10,20,50,100]
    for kk in tmp:
        for i in range(kk,n+1):
            dp[i]+=dp[i-kk]
    print(dp[n])

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关【暴力DP】2021 icpc上海 I

[Problem - I - Codeforces][] 题意： ![01d23059f1114440bc2d82d7f8bf21f3.png][] ![83f6684a

谁践踏了优雅/ 2024年03月26日 22:21/ 0 赞/ 69 阅读

相关【暴力DP】CF1409 F

[Problem - F - Codeforces][] 题意： ![0b383875a1444f75b1163b33ac695a0b.png][] ![e01ceb20

骑猪看日落/ 2024年03月01日 07:49/ 0 赞/ 48 阅读

相关 POJ 1661 暴力dp

题意略。思路：很有意思的一个题，我采用的是主动更新未知点的方式，也即刷表法来dp。我们可以把整个路径划分成横向移动和纵向移动，题目一开始就给出了Jimmy的高度，这

绝地灬酷狼/ 2023年08月17日 16:37/ 0 赞/ 118 阅读

相关【dp/二分+暴力】MAGRID UVALive - 5983

Think: 1知识点：dp/二分+暴力 2题意：从(1, 1)点到达(n, m)点，每经过一个点可能会失去能量或者得到能量，询问最小的出发能量使得存在一条路径，路径经

╰半夏微凉°/ 2022年06月09日 14:26/ 0 赞/ 147 阅读

相关简单暴力到dp的优化（入门篇）

上篇，我们提到，遇到问题，首先根据定义写出笨方法，找出依赖关系（有些题这一步就不太简单，要自己归纳关系），然后进行优化，下面，我们通过几道此方面的经典的，较为简单的二维题目进行

淡淡的烟草味﹌/ 2022年05月27日 09:55/ 0 赞/ 158 阅读

相关简单暴力到dp的优化（萌新篇）

想写一系列文章，总结一些题目，看看解决问题、优化方法的过程到底是什么样子的。系列问题一：斐波那契数列问题在数学上，斐波纳契数列以如下被以[递归][Link 1]的方

小灰灰/ 2022年05月26日 21:05/ 0 赞/ 172 阅读

相关简单暴力到dp的优化(初级篇）

一、一维非脑残 1 一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串

左手的ㄟ右手/ 2022年05月25日 02:06/ 0 赞/ 116 阅读

相关简单暴力到dp的优化(中级篇）

下面再放三道我比较喜欢的，需要好好写一下的题。第一题比较水 1. White Cloud is exercising in the playground. White C

女爷i/ 2022年05月18日 05:48/ 0 赞/ 133 阅读

相关四边形优化dp入门

参考博客： [https://www.cnblogs.com/zxndgv/archive/2011/08/02/2125242.html][https_www.cnb

红太狼/ 2021年12月14日 02:15/ 0 赞/ 307 阅读

相关 RabbitMQ入门到精通（入门篇）

RabbitMQ 一. 初识 1. 什么是MQ > 官方解释 MQ（Message Queue）消息队列，是基础数据结构中“先进先出”的一种数据结构。

た入场券/ 2021年09月25日 14:04/ 0 赞/ 694 阅读