[已解决]Python：每日一题 373

zltzlt

今天的题目：

假设你正在爬楼梯。给定数组 cost，数组的每个索引做为一个阶梯，第 n 个阶梯对应着一个非负数的体力值 cost[n]。

每当爬上一个阶梯都要花费对应的体力值，然后你可以选择继续爬一个阶梯或者两个。

找到达到楼层顶部的最低体力花费。

在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20]
输出：15
解释：从 cost[1] 开始，走两步即可到阶梯顶，一共花费 15 点体力值。

示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：从 cost[0] 开始，逐个经过那些 1（跳过 cost[3]），一共花费 6 点体力值。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-4-11 20:06:38

最简单的方法，利用递推式进行循环迭代，比dp快

def fun373(cost):
    #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
    M = len(cost)
    if M == 1:
        return cost[0]
    elif M == 2:
        return min(cost[0],cost[1])
    a = cost[-2]
    b = cost[-1]
    for index in range(M - 3,-1,-1):
        a,b = min(a,b)+cost[index],a
    return  min(a,b) 

跳转到最佳答案楼层

_2_

依然不懂……
或者说多举一点例子

zltzlt

_2_ 发表于 2020-4-11 19:04
依然不懂……
或者说多举一点例子

输入：cost = [2, 3, 4, 5, 6]
输出：8

2, 3, 4, 5, 6, 阶梯顶部

_2_

zltzlt 发表于 2020-4-11 19:08
输入：cost = [2, 3, 4, 5, 6]
输出：8

最小？

_2_

zltzlt 发表于 2020-4-11 19:08
输入：cost = [2, 3, 4, 5, 6]
输出：8

OK我明白了

永恒的蓝色梦想

瞎写了个，竟然过了……

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cost=cost.__iter__()
        a=cost.__next__()
        b=cost.__next__()

        for i in cost:
            a,b=b,min(a,b)+i

        return min(a,b)

整体思路就是动态规划，因为一次只能上一节或两节，所以只和前面的两个值有关，用两个变量就可以了。

TJBEST

最简单的方法，利用递推式进行循环迭代，比dp快

def fun373(cost):
    #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
    M = len(cost)
    if M == 1:
        return cost[0]
    elif M == 2:
        return min(cost[0],cost[1])
    a = cost[-2]
    b = cost[-1]
    for index in range(M - 3,-1,-1):
        a,b = min(a,b)+cost[index],a
    return  min(a,b) 

zltzlt

TJBEST 发表于 2020-4-11 20:06
前排占座，另372题先别封还在做@zltzlt

塔利班

def f373(cost):
    l=len(cost)
    t=[0]*(l+1)
    for i in range(2,l+1):
        t[i]=min(t[i-1]+cost[i-1],t[i-2]+cost[i-2])
    return t[l]

风魔孤行者

def f(cost):
    if len(cost)<=2:
        return min(cost)
    elif len(cost) == 3:
        if cost[1] < cost[0]+cost[2]:
            return cost[1]
        else:
            return cost[0]+cost[2]
    else:
        return min(cost[len(cost)-1]+f(cost[:len(cost)-1]),cost[len(cost)-2]+f(cost[:len(cost)-2]))

kinkon

虽然测试用例是对的，但是总感觉哪里有问题

def f373(cost):
    if len(cost) <= 2:
        return min(cost)
    cost.append(0)
    left = 2
    while left < len(cost):
        cost[left] = min(cost[left-1], cost[left-2]) + cost[left]
        left = left+1
    return cost[-1]

空间换时间

def p373(cost):
    if len(cost) <=2:
        return min(cost)
    cost.append(0)
    dp = [0]*len(cost)
    dp[0],dp[1]=cost[0],cost[1]
    for c in range(2, len(cost)):
        dp[c] = min(dp[c-2],dp[c-1])+cost[c]
    return dp[c]

l0stparadise

def f373(cost):
    dp = [0]*(len(cost))
    dp[0] =cost[0]
    dp[1] = cost[1]
    stairs = len(cost)
    for i in range(2,stairs):
        dp[i] = min(dp[i-1]+cost[i],dp[i-2]+cost[i])
    return min(dp[-2],dp[-1])

山岂乎不在高

[ 本帖最后由 山岂乎不在高 于 2020-4-13 00:10 编辑 ]\n\ndef p373(a):
    s=0
    a=[0]+a+[0]
    while True:
        if sum(a)==0:
            return s
        i=a.index(max(a))
        s+=a[i+1]+a[i-1]
        a[i]=a[i-1]=a[i+1]=0

钙硼钡锗

d=[]
def f373(cost):
    d=[]
    for i in range(int('1'*len(cost),2)+1):
        b=0
        c=[]
        a=bin(i).replace('0b','').zfill(len(cost))
        for j in str(a):
            b+=int(j)+1
            if b>len(cost):break
            else:c.append(cost[b-1])
        n=0
        for j in c:
            n+=j
        d.append(n)
    print(min(d))

阴阳神万物主

难度评级：简单
要素分析：贪心
代码：

def solve(cost:'list of int >=0')->int:
    i,u = -1,0
    while i < len(cost)-4:#结束循环后最多只剩3级台阶要上
        a,b = i+1,i+2
        i = a if cost[a]<cost[b] else b
        u += cost[i]
    return u+min(sum(cost[i+1::+2]),sum(cost[i+2::+2]))

if __name__ == '__main__':
    print('示例1 输出：',solve([10, 15, 20]))
    print('示例2 输出：',solve([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
    print('自测 输出：',solve([1,1]))

xiangjianshinan

怎么越想越难呢？？？

March2615

每天只能刷到前一天的我也是不懂

# 动态规划
# dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

def daily373_1(cost: list) -> int:
    length = len(cost)
    dp = [0 for _ in range(length)]
    dp[0], dp[1] = cost[0], cost[1]
    for i in range(2, length):
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
    return min(dp[length - 1], dp[length - 2])

发现只与前两个有关，可以只用两个变量记录而不用数组

def daily373_2(cost: list) -> int:
    pre, ppre = 0, 0
    for i in range(len(cost)):
        pre, ppre = min(pre, ppre) + cost[i], pre
    return min(pre, ppre)

爱叫什么叫什么

我还是小白,还不懂...

whosyourdaddy

def func373(cost):
    n = len(cost)
    for i in range(2,n):
        cost[i] += min(cost[i-1],cost[i-2])
    return min(cost[-1],cost[-2])

扁扁

观摩大佬们的解答