題目描述

一只袋鼠要從河這邊跳到河對岸，河很寬，但是河中間打了很多樁子，每隔一米就有一個，每個樁子上都有一個彈簧，袋鼠跳到彈簧上就可以跳的更遠。每個彈簧力量不同，用一個數字代表它的力量，如果彈簧力量為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

總結

以上是生活随笔為你收集整理的袋鼠过河（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。