题解 | 小红的地砖
小红的地砖
https://www.nowcoder.com/practice/8cd083c66a5f43489a532164e2a2304d
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 a =in.nextInt();
int s[]=new int[a];
int dp[]=new int[a];
for(int i=0;i<a;i++){
s[i]=in.nextInt();
}
dp[0]=0;
dp[1]=s[1];
for(int i=2;i<a;i++){
dp[i]=Math.min(s[i]+dp[i-1],s[i]+dp[i-2]);
}
System.out.print(dp[a-1]);
}
}
状态转移方程： dp[i]=Math.min(s[i]+dp[i-1],s[i]+dp[i-2]);
dp[i]:到达第i个阶梯花费最少体力
到达第i个阶梯有两条路
一：从i-2处走两步到i，花费体力：到达i-2处最少体力+i阶梯体力
二：从i-1处走两步到i，花费体力：到达i-1处最少体力+i阶梯体力
所以到达i阶梯最终体力等于两者最小： dp[i]=Math.min(s[i]+dp[i-1],s[i]+dp[i-2]);
投递京东等公司10个岗位