门户网站是如何盈利的,wordpress远程安装,湖北交投建设集团有限公司网站,室内设计说明500字简约上篇#xff0c;我们提到#xff0c;遇到问题#xff0c;首先根据定义写出笨方法#xff0c;找出依赖关系#xff08;有些题这一步就不太简单#xff0c;要自己归纳关系#xff09;#xff0c;然后进行优化#xff0c;下面#xff0c;我们通过几道此方面的经典的我们提到遇到问题首先根据定义写出笨方法找出依赖关系有些题这一步就不太简单要自己归纳关系然后进行优化下面我们通过几道此方面的经典的较为简单的二维题目进行讲解。 开始根据题来说明
第一个萌新题
给定数组arr, arr 中所有的值都为正数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张 再给定一个整数aim 代表要找的钱数求组成aim 的最少货币数。 [举例] arr[5,2,3], aim20。 4 张5 元可以组成20 元其他的找钱方案都要使用更多张的货币返回4。
arr[5,2,3], aim0。 不用任何货币就可以组成0 元返回0。 arr[3,5],aim2。 根本无法组成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),k0,且b-k*arr[a]0
当然以前也提到过直接递归我们会有大量重复计算所以需要记下来之前的结果供我们使用。有两个参数代表现在的状态所以生成二维表。
l[[0 for i in range(len(arr))] for i in range(aim1)]#
我们看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用来记录当前的最小路径和
以后也不分析暴力的时间复杂度了
对于普遍的位置ij只有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即可
nint(input())
dp[0]*(n1)
dp[0]1
tmp[1,5,10,20,50,100]
for kk in tmp:for i in range(kk,n1):dp[i]dp[i-kk]
print(dp[n])
