codancer爬楼梯问题的算法笔试模拟题详解

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第113题：codancer上楼 的题目解析，具体如下：

题目描述

题目等级：中等
知识点：DP

查看题目：codancer上楼
codancer来到了一栋大楼前，现在他要上楼。

如果codancer从第x层走楼梯到第y层(y>x)，那么他所花费的时间是a[x]+a[x+1]+…+a[y]；

如果他从x层坐电梯到第y层，那么他所花费的时间是c+(b[x]+b[x+1]+…+b[y])，因为他等电梯的时间为c。

现在codancer想知道 从第1层到第n层需要最少需要多长时间？

有四个入参，第一个输入一个正整数n，表示要上到第n层楼；

第二个输入一个整数c(1<=n<=100000,1<=c<=1000)，表示等电梯花费的时间；
接下来输入两个数组a和b，数组中n-1个数字代表数组a和b(1<=a[i],b[i]<=1000)，分别表示爬楼梯和乘电梯每层楼花费的时间。

输出codancer到达第n层最少需要的时间。

示例1
输入：
4
1
[3,2,3]
[1,2,3]
输出：
7
注意
直接坐电梯从1楼到4楼即可，答案是1+1+2+3=7

解题思路：动态规划

对于每层需要保存两个值。一个是这层选择选择走楼梯的最小花费，记为Ta(i)。另一个是这层选择坐电梯的最小花费，记为Tb(i)。

状态转移（字母与题干中所给含义相同）

Ta(i+1) = min(Ta(i)+a(i+1)，Tb(i)+a(i+1))
Tb(i+1) = min(Ta(i)+b(i+1)+c，Tb(i)+b(i+1))

这样一直计算到最后一层即可。

时间复杂度O(n)
空间复杂度O(2*n)

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：codancer上楼