[已解决]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快

1. def fun373(cost):
   
2.     #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
   
3.     M = len(cost)
   
4.     if M == 1:
   
5.         return cost[0]
   
6.     elif M == 2:
   
7.         return min(cost[0],cost[1])
   
8.     a = cost[-2]
   
9.     b = cost[-1]
   
10.     for index in range(M - 3,-1,-1):
    
11.         a,b = min(a,b)+cost[index],a
    
12.     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我明白了

永恒的蓝色梦想

瞎写了个，竟然过了……

1. class Solution:
   
2.     def minCostClimbingStairs(self, cost: List[int]) -> int:
   
3.         cost=cost.__iter__()
   
4.         a=cost.__next__()
   
5.         b=cost.__next__()
   
6. 
   
7.         for i in cost:
   
8.             a,b=b,min(a,b)+i
   
9. 
   
10.         return min(a,b)

复制代码

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

TJBEST

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

1. def fun373(cost):
   
2.     #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
   
3.     M = len(cost)
   
4.     if M == 1:
   
5.         return cost[0]
   
6.     elif M == 2:
   
7.         return min(cost[0],cost[1])
   
8.     a = cost[-2]
   
9.     b = cost[-1]
   
10.     for index in range(M - 3,-1,-1):
    
11.         a,b = min(a,b)+cost[index],a
    
12.     return  min(a,b)

复制代码

zltzlt

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

塔利班

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

复制代码

风魔孤行者

1. def f(cost):
   
2.     if len(cost)<=2:
   
3.         return min(cost)
   
4.     elif len(cost) == 3:
   
5.         if cost[1] < cost[0]+cost[2]:
   
6.             return cost[1]
   
7.         else:
   
8.             return cost[0]+cost[2]
   
9.     else:
   
10.         return min(cost[len(cost)-1]+f(cost[:len(cost)-1]),cost[len(cost)-2]+f(cost[:len(cost)-2]))

复制代码

kinkon

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

1. def f373(cost):
   
2.     if len(cost) <= 2:
   
3.         return min(cost)
   
4.     cost.append(0)
   
5.     left = 2
   
6.     while left < len(cost):
   
7.         cost[left] = min(cost[left-1], cost[left-2]) + cost[left]
   
8.         left = left+1
   
9.     return cost[-1]

复制代码

空间换时间

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

复制代码

l0stparadise

1. def f373(cost):
   
2.     dp = [0]*(len(cost))
   
3.     dp[0] =cost[0]
   
4.     dp[1] = cost[1]
   
5.     stairs = len(cost)
   
6.     for i in range(2,stairs):
   
7.         dp[i] = min(dp[i-1]+cost[i],dp[i-2]+cost[i])
   
8.     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

钙硼钡锗

1. d=[]
   
2. def f373(cost):
   
3.     d=[]
   
4.     for i in range(int('1'*len(cost),2)+1):
   
5.         b=0
   
6.         c=[]
   
7.         a=bin(i).replace('0b','').zfill(len(cost))
   
8.         for j in str(a):
   
9.             b+=int(j)+1
   
10.             if b>len(cost):break
    
11.             else:c.append(cost[b-1])
    
12.         n=0
    
13.         for j in c:
    
14.             n+=j
    
15.         d.append(n)
    
16.     print(min(d))

复制代码

阴阳神万物主

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

1. def solve(cost:'list of int >=0')->int:
   
2.     i,u = -1,0
   
3.     while i < len(cost)-4:#结束循环后最多只剩3级台阶要上
   
4.         a,b = i+1,i+2
   
5.         i = a if cost[a]<cost[b] else b
   
6.         u += cost[i]
   
7.     return u+min(sum(cost[i+1::+2]),sum(cost[i+2::+2]))
   
8. 
   
9. if __name__ == '__main__':
   
10.     print('示例1 输出：',solve([10, 15, 20]))
    
11.     print('示例2 输出：',solve([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
    
12.     print('自测 输出：',solve([1,1]))
    

复制代码

xiangjianshinan

怎么越想越难呢？？？

March2615

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

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

复制代码

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

复制代码

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

1. def daily373_2(cost: list) -> int:
   
2.     pre, ppre = 0, 0
   
3.     for i in range(len(cost)):
   
4.         pre, ppre = min(pre, ppre) + cost[i], pre
   
5.     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])

扁扁

观摩大佬们的解答