论坛 › Python交流 › Python：每日一题 373

zltzlt 发表于 2020-4-11 18:58:43

Python：每日一题 373

今天的题目：

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

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

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

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

示例 1：

输入：cost =
输出：15
解释：从 cost 开始，走两步即可到阶梯顶，一共花费 15 点体力值。
示例 2：

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

{:10_298:}欢迎大家一起答题！{:10_298:}

_2_ 发表于 2020-4-11 19:04:59

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

zltzlt 发表于 2020-4-11 19:08:34

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

输入：cost =
输出：8

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

_2_ 发表于 2020-4-11 19:09:54

zltzlt 发表于 2020-4-11 19:08
输入：cost =
输出：8



最小？

_2_ 发表于 2020-4-11 19:10:28

zltzlt 发表于 2020-4-11 19:08
输入：cost =
输出：8



OK我明白了

永恒的蓝色梦想 发表于 2020-4-11 19:48:12

本帖最后由 永恒的蓝色梦想 于 2020-4-11 21:31 编辑

瞎写了个，竟然过了……class Solution:
    def minCostClimbingStairs(self, cost: List) -> 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 发表于 2020-4-11 20:06:38

本帖最后由 TJBEST 于 2020-4-11 22:08 编辑

最简单的方法，利用递推式进行循环迭代，比dp快
def fun373(cost):
    #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
    M = len(cost)
    if M == 1:
      return cost
    elif M == 2:
      return min(cost,cost)
    a = cost[-2]
    b = cost[-1]
    for index in range(M - 3,-1,-1):
      a,b = min(a,b)+cost,a
    returnmin(a,b)

zltzlt 发表于 2020-4-11 20:07:39

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

{:10_323:}

塔利班 发表于 2020-4-11 20:36:01

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

风魔孤行者 发表于 2020-4-11 22:15:12

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

kinkon 发表于 2020-4-11 22:30:33

本帖最后由 kinkon 于 2020-4-12 12:45 编辑

虽然测试用例是对的，但是总感觉哪里有问题
def f373(cost):
    if len(cost) <= 2:
      return min(cost)
    cost.append(0)
    left = 2
    while left < len(cost):
      cost = min(cost, cost) + cost
      left = left+1
    return cost[-1]
空间换时间
def p373(cost):
    if len(cost) <=2:
      return min(cost)
    cost.append(0)
    dp = *len(cost)
    dp,dp=cost,cost
    for c in range(2, len(cost)):
      dp = min(dp,dp)+cost
    return dp

l0stparadise 发表于 2020-4-11 23:26:54

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

山岂乎不在高 发表于 2020-4-12 00:20:10

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

钙硼钡锗 发表于 2020-4-12 00:58:36

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)
      n=0
      for j in c:
            n+=j
      d.append(n)
    print(min(d))

阴阳神万物主 发表于 2020-4-12 02:22:11

本帖最后由 阴阳神万物主 于 2020-4-12 02:44 编辑

难度评级：简单
要素分析：贪心
代码：
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<cost else b
      u += cost
    return u+min(sum(cost),sum(cost))

if __name__ == '__main__':
    print('示例1 输出：',solve())
    print('示例2 输出：',solve())
    print('自测 输出：',solve())

xiangjianshinan 发表于 2020-4-12 04:10:12

怎么越想越难呢？？？

March2615 发表于 2020-4-12 18:57:33

每天只能刷到前一天的我也是不懂
# 动态规划
# dp = cost + min(dp, dp)
def daily373_1(cost: list) -> int:
    length = len(cost)
    dp =
    dp, dp = cost, cost
    for i in range(2, length):
      dp = min(dp, dp) + cost
    return min(dp, dp)
发现只与前两个有关，可以只用两个变量记录而不用数组
def daily373_2(cost: list) -> int:
    pre, ppre = 0, 0
    for i in range(len(cost)):
      pre, ppre = min(pre, ppre) + cost, pre
    return min(pre, ppre)

爱叫什么叫什么 发表于 2020-4-12 21:34:20

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

whosyourdaddy 发表于 2020-4-12 22:47:35

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

扁扁 发表于 2020-4-12 23:13:35

观摩大佬们的解答

查看完整版本: Python：每日一题 373