Ignite

袋鼠过河

2017-08-23

最近忙着复习,博客就更新频率少低了,现在就先把觉得重要的算法题记录一下,在牛客网上做到的最简单的动态规划问题,当然这道题的变形在leetCode上也有(jumpGame)。

题目描述

一只袋鼠要从河这边跳到河对岸,河很宽,但是河中间打了很多桩子,每隔一米就有一个,每个桩子上都有一个弹簧,袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同,用一个数字代表它的力量,如果弹簧力量为5,就代表袋鼠下一跳最多能够跳5米,如果为0,就会陷进去无法继续跳跃。河流一共N米宽,袋鼠初始位置就在第一个弹簧上面,要跳到最后一个弹簧之后就算过河了,给定每个弹簧的力量,求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1

输入描述:

输入分两行,第一行是数组长度N (1 ≤ N ≤ 10000),第二行是每一项的值,用空格分隔。

输出描述:

输出最少的跳数,无法到达输出-1

示例1

输入
5
2 0 1 1 1
输出
4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Jump {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] nums = new int[N + 1];
int[] dp = new int[N + 1];
for (int i = 0; i < N; i++)
nums[i] = sc.nextInt();

for (int i = 0; i <=N; i++)
dp[i] = 100000;
nums[N] = 1;
dp[0] = 0;
for (int i = 1; i <= N; i++) {
if (nums[i] == 0)
continue;
for (int j = 0; j < i; j++) {
if (nums[j] >= i - j)
dp[i] = Math.min(dp[j] + 1, dp[i]);
System.out.println("i=" + i + "," + "j=" + j + " " + "dp[" + i + "]: " + dp[i]);

}

}
System.out.println((dp[N] == 100000) ? -1 : dp[N]);

}

}
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章