简单暴力到dp的优化(入门篇)
上篇,我们提到,遇到问题,首先根据定义写出笨方法,找出依赖关系(有些题这一步就不太简单,要自己归纳关系),然后进行优化,下面,我们通过几道此方面的经典的,较为简单的二维题目进行讲解。
开始根据题来说明:
第一个萌新题
给定数组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])
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/79964233
- 点赞
- 收藏
- 关注作者
评论(0)