你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
数据范围:数组长度满足 ,数组中的值满足
第一行输入一个正整数 n ,表示数组 cost 的长度。第二行输入 n 个正整数,表示数组 cost 的值。
输出最低花费
3 2 5 20
5
你将从下标为1的台阶开始,支付5 ,向上爬两个台阶,到达楼梯顶部。总花费为5
10 1 100 1 1 1 90 1 1 80 1
6
你将从下标为 0 的台阶开始。 1.支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。 2.支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。 3.支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。 4.支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。 5.支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。 6.支付 1 ,向上爬一个台阶,到达楼梯顶部。 总花费为 6 。
#include<stdlib.h> #include<algorithm> using namespace std; int main(){ int n; while(scanf("%d",&n)!=EOF){ int *cost=(int *)malloc(sizeof(int)*(n+2)); int *dp=(int *)malloc(sizeof(int)*(n+2)); for(int i=1;i<=n;i++){ scanf("%d",&cost[i]); } dp[1]=0; dp[2]=0; dp[3]=min(dp[1]+cost[1],dp[2]+cost[2]); for(int i=4;i<=n+1;i++) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); printf("%d\n",dp[n+1]); } return 0; }
#include <iostream> using namespace std; int main() { int n; cin >> n; if (n < 2) { cout << 0; return 0; } int arr[n]; for (int i = 0; i < n; ++i) cin >> arr[i]; // 时间复杂度O(N),空间复杂度O(1) int dp0 = 0, dp1 = 0, dp2; for (int i = 2; i <= n; ++i) { dp2 = min(dp0 + arr[i - 2], dp1 + arr[i - 1]); dp0 = dp1; dp1 = dp2; } cout << dp2; return 0; }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int n = in.nextInt(); int []arr = new int[n + 1]; for (int i = 0; i < n; i++) arr[i] = in.nextInt(); int []dp = new int[n + 1]; dp[0] = dp[1] = 0; for (int i = 2; i <= n; i++) dp[i] = Math.min(dp[i - 1] + arr[i - 1], dp[i - 2] + arr[i - 2]); System.out.println(dp[n]); } }
#include <iostream> using namespace std; int main() { int n; cin>>n; int st[n+1]; int cost[n+1]; for(int i=0;i<n;i++) { cin>>st[i]; cost[i]=0x3f3f3f3f; } cost[n] = 0x3f3f3f3f; cost[1]=cost[0]=0; for(int i=0;i<=n;i++) { for(int s=i-2;s<i;s++) { if(s<0)continue; cost[i]=min(cost[i],cost[s]+st[s]); } } cout<<cost[n]; }
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { let n = (await readline()).split(" ")[0]; let stairs = (await readline()).split(" "); let arr = [] stairs.forEach(e => { arr.push(parseInt(e)) }) function minCost(num, cost) { if(num == 1) { return 0 } let res = new Array(n) res[num - 1] = 0 res[num - 2] = cost[num - 2] < cost[num - 1] ? cost[num - 2]:cost[num - 1] for(let i = num - 3; i >= 0; i--) { if(cost[i] + res[i + 1] <= cost[i + 1] + res[i + 2]) { res[i] = cost[i] + res[i + 1] } else { res[i] = cost[i + 1] + res[i + 2] } } return res[0] } console.log(minCost(n, arr)); })();
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int[] cost = new int[in.nextInt()]; for(int i = 0;i<cost.length;i++){ cost[i] = in.nextInt(); } int result = ComputeMinCost(cost); System.out.println(result); } public static int ComputeMinCost(int[] cost){ //定义dp数组 int length = cost.length; int[] dp = new int[length+1]; //初始化dp数组 dp[0] = 0; dp[1] = 0; //遍历数组 for(int i =2;i<=length;i++){ dp[i] = Math.min(dp[i-1]+cost[i-1] , dp[i-2] + cost[i-2] ); } return dp[length]; } }
#include <stdio.h> #include <string.h> #define MaxCost 1000000 int jumpStep(int* cost,int costLen); int main() { int cost[MaxCost]; int costLen = 0; while(scanf("%d",&costLen)!=EOF){ memset(cost,0,sizeof(int)*costLen); int i = 0; for(i = 0;i < costLen;i++) scanf("%d",&cost[i]); int result = 0; result = jumpStep(cost, costLen); printf("%d\n",result); } return 0; } int jumpStep(int* cost,int costLen){ if(costLen == 1 || costLen == 2) return 0; int dp[MaxCost]; memset(dp,0, costLen*sizeof(int)); dp[0] = 0; dp[1] = 0; int i = 0; for(i = 2; i<costLen;i++){ dp[i] = dp[i-1]+cost[i-1]<dp[i-2]+cost[i-2]?dp[i-1]+cost[i-1]:dp[i-2]+cost[i-2]; } return dp[costLen-1]+cost[costLen-1]<dp[costLen-2]+cost[costLen-2]?dp[costLen-1]+cost[costLen-1]:dp[costLen-2]+cost[costLen-2]; }
package main import ( "fmt" ) func main() { var n int fmt.Scanf("%d",&n) var arr []int var x int for n>0{ fmt.Scanf("%d",&x) arr=append(arr,x) n-- } if len(arr)==1{ fmt.Println(arr[0]) return } dp:=make([]int,len(arr)) dp[0]=arr[0] dp[1]=arr[1] for i:=2;i<len(arr);i++{ dp[i]=min(dp[i-1],dp[i-2])+arr[i] } fmt.Println(min(dp[len(dp)-1],dp[len(dp)-2])) } func min(a,b int)int{ if a<b{ return a } return b }
#include <iostream> using namespace std; #include <vector> int a[100005]; int main() { int n; cin >> n; vector<int> v(n); for(int i = 0; i < n; ++i) cin >> v[i]; for(int i = 2; i <= n; ++i) { a[i] = min(a[i-1] + v[i-1], a[i-2] + v[i-2]); } cout << a[n] << endl; } // 64 位输出请用 printf("%lld")
package main import ( "fmt" ) func main() { a := 0 fmt.Scan(&a) cost := make([]int,a + 1) for i := 0;i <= a;i++ { fmt.Scan(&cost[i]) } dp := make([]int,a + 1) dp[0] = 0 dp[1] = 0 for i := 2; i <= a;i++ { dp[i] = min(dp[i-2] + cost[i-2],dp[i-1] + cost[i-1]) } fmt.Println(dp[a]) } func min(a,b int) int { if a < b { return a } return b }
import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s; while ((s = br.readLine()) != null) { int n = Integer.parseInt(s); int[] cost = new int[n]; String[] numStr = br.readLine().split(" "); for (int i = 0; i < n; i++) { cost[i] = Integer.parseInt(numStr[i]); } int[] dp = new int[n + 1]; for (int i = 2; i <= n; i++) { dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]); } System.out.println(dp[n]); } } }
while(n = +readline()){ var lines = readline().split(' ') lines.forEach(function(ele,index){ lines[index] = +ele; }); var length = lines.length; var res = new Array(length+1); res[0]=0; if(length>0){ res[1]=0 } for (let i =1;i<length;i++){ res[i+1] = res[i]+lines[i]>res[i-1]+lines[i-1]?res[i-1]+lines[i-1]:res[i]+lines[i]; } // console.log(res) console.log(res[length]) }