刷题时碰到的一个简单的接收问题
##题目来自leecode 764.使用最小花费爬楼梯问题
""" 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。 一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 示例 1: 输入:cost = [10,15,20] 输出:15 解释:你将从下标为 1 的台阶开始。 - 支付 15 ,向上爬两个台阶,到达楼梯顶部。 总花费为 15 """
这一道题可以先用暴力dfs解出范例,然后再用记忆化搜索进行进一步优化,最后可以使用正序dp或者倒序dp进行进一步优化。
不过,我想讲一下python该如何快捷接收这个数据 list
就是使用eval()函数,这个函数具体就是把接收的数据转换为相应的正确类型,很方便
那么在这里,我就把题解写了:
1.直接暴力dfs
cost = eval(input()) #接收数组
#下标就是它对应的台阶 数组最终长度就是最终目标
def dfs(x):
if x == 0 or x == 1:
return 0 #没有方案
else:
#这里的意思就是下一/两阶台阶并加上对应的花费
res = min(dfs(x-1)+cost[x-1],dfs(x-2)+cost[x-2])
return res
print(dfs(len(cost))
2.优化,记忆化搜索
cost = eval(input()) #接收数组
#下标就是它对应的台阶 数组最终长度就是最终目标
N = 1010 #设定记忆化数组大小范围
mem = [0 for i in range(N)]
def dfs(x):
if mem[x]:
return mem[x]
if x == 0 or x == 1:
return 0 #没有方案
else:
#这里的意思就是下一/两阶台阶并加上对应的花费
res = min(dfs(x-1)+cost[x-1],dfs(x-2)+cost[x-2])
mem[x] = res
return res
print(dfs(len(cost))
3.倒序dp优化
就是从递归的“归操作”进行模拟
我们从这个根为5的递归搜索数的最小子叶0,1进行模拟
cost = eval(int,input())
N = 1010 #设一个尽量比测试范围大一些的数
f = [0 for i in range(N)]
n = len(cost)
f[0] = f[1] = 0 #先初始化一下 ,这道题刚好都是0
#可以不用初始化,但是其他就需要初始化一下
#开始倒序模拟 递推到根结点
for i in range(2,n+1):
f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2])
print(f[n])
"""
可以看到,这个枚举的操作就是复刻了那个递归的“归”操作
"""
原文地址:https://blog.csdn.net/2301_80246346/article/details/137498387
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!