首页 > 袋鼠过河(动态规划)

袋鼠过河(动态规划)

题目描述

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

输入描述:

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

输出描述:

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

输入

5
2 0 1 1 1

输出

4
 1 import java.util.ArrayList;
 2 import java.util.List;
 3 import java.util.Scanner;
 4 /**
 5  * 
 6  * 袋鼠过河(最多跳弹簧的步数) 用 list 来模拟dp数组 list存每一行,横坐标为 各个弹簧的到达情况 未到达为0 到达为1 到达此处陷入为0
 7  * 
 8  * @author Dell
 9  *
10  */
11 public class Main {
12     static List<int[]> dp = new ArrayList();
13     static int n;
14     static int[] is;
15 
16     static int f() {
17         // 站在第一个弹簧上时
18         int step = 0;
19         int x = 0;
20         int[] s = new int[n + 1];
21         for (int j = 0; j < s.length; j++) {
22             s[j] = 0;
23         }
24         s[0] = 1;
25         dp.add(s);
26         while (step <= n) { // 所有行
27             int[] ss = new int[n + 1];// 多出来的最后一位表示岸上
28             for (int j = 0; j < ss.length; j++) {
29                 ss[j] = 0;
30             }
31             // 每一行 根据本行填写下一行
32             for (int i = step; i < ss.length; i++) { // 多出来的最后一位表示岸上
33                 // 位置 i已到达
34                 if (dp.get(dp.size() - 1)[i] == 1) {
35                     // 走不同的步数
36                     for (int j = 1; j <= is[i]; j++) {
37                         // 判断不可超出弹簧范围一个一,下标要多减,若超出则选岸上为1
38                         if (i + j <= ss.length-2) { 
39                             // 在范围内 新位置 不是0 不会陷 访问
40                             if (is[i + j] > 0) {
41                                 ss[i + j] = 1;
42                             }
43                         } else {
44                             // 超出则选最后一个为1
45                             ss[ss.length - 1] = 1;
46                         }
47                 }
48                 }
49             }
50             dp.add(ss);
51 
52             step++;
53             if (dp.get(dp.size()-1)[ss.length - 1] == 1) { // 岸上访问到
54                 return step;
55             }
56         }
57         return -1;
58     }
59     public static void main(String[] args) {
60         Scanner sc = new Scanner(System.in);
61         n = sc.nextInt();
62         is = new int[n];
63         for (int i = 0; i < is.length; i++) {
64             is[i] = sc.nextInt();
65         }
66         int res = f();
67         System.out.println(res);
68     }
69 }

 

转载于:https://www.cnblogs.com/the-wang/p/8981592.html

更多相关:

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...