首页 > 试题广场 >

最小代价爬楼梯

[编程题]最小代价爬楼梯
  • 热度指数：9151 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你需要爬上一个 n 层的楼梯，在爬楼梯过程中， 每阶楼梯需花费非负代价，第i阶楼梯花费代价表示为 cost[i] ， 一旦你付出了代价，你可以在该阶基础上往上爬一阶或两阶。
你可以从第 0 阶或者 第 1 阶开始，请找到到达顶层的最小的代价是多少。
n 和 cost[i] 皆为整数

数据范围： ,

输入描述:
输入为一串半角逗号分割的整数，对应cost数组，例如

10,15,20


输出描述:
输出一个整数，表示花费的最小代价
示例1

输入

1,100,1,1,1,100,1,1,100,1

输出

6
算法知识视频讲解
添加回答
Python
外包不准吃公司零食头像 外包不准吃公司零食

Python 动态规划

dp[i] = min(dp[i-1]+L[i-1],dp[i-2]+L[i-2])

注意可以花费0代价调到第0或第1层 


import sys
L = list(map(int, sys.stdin.readline().strip().split(',')))
if len(L)<=2:
    print(min(L))
else:
    dp = [0]*len(L)
    for i in range(2, len(L)):
        dp[i] = min(dp[i-1]+L[i-1], dp[i-2]+L[i-2])
    print(min(dp[-1]+L[-1], dp[-2]+L[-2]))


编辑于 2020-02-17 22:30:21 回复(0)
Python
贾志统头像 贾志统 
def min_cost3(cost):
    dp = [0, 0]
    for single_cost in cost:
        dp.append(single_cost + min(dp[-1], dp[-2]))
    print(min(dp[-1], dp[-2]))


cost = list(map(int, input().split(",")))
min_cost3(cost)

发表于 2019-08-22 23:50:00 回复(0)
Python
欧巴禾头像 欧巴禾
while True:
    try:
        arr = [int(elem) for elem in input().split(',')]
        n = len(arr)
        dp = [0]*(n+1)
        dp[0] = 0; dp[1] = 0
        for i in range(2, n+1):
            dp[i] = min(arr[i-2]+dp[i-2], arr[i-1]+dp[i-1])
        print(dp[n])
    except:
        break
发表于 2019-08-09 18:19:28 回复(0)
Python
北雷北雷头像 北雷北雷

动态规划
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
其中dp[0]=dp[1]=0;

import sys
words = sys.stdin.readline()
words = words.strip()
words = words.split(',')
costs = [int(x) for x in words]

dp=[None]*(len(words)+1)
if len(costs)<3:
    print(1)
    exit()
dp[0]=dp[1]=0
for i in range(2,len(words)+1):
    dp[i] = min(dp[i-1]+costs[i-1],dp[i-2]+costs[i-2])

print(dp[-1])
发表于 2019-07-14 21:38:25 回复(0)
Python
ElonB头像 ElonB 
"""
台阶问题，考虑动态规划
设dp[i]为到达第i层的最小花费，
dp[i] = min(dp[i - 1], dp[i - 2]) + a[i]
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split(',')))
    a.append(0)
    dp = [a[0], a[1]]
    for i in range(2, len(a)):
        dp.append(min(dp[i - 1], dp[i - 2]) + a[i])
    print(dp[-1])

发表于 2019-07-10 14:47:23 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 动态规划 安卓工程师 快手 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 2019 Java工程师
上传者：小小
难度：
5条回答 9800浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最小代价爬楼梯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号