袋鼠过河（动态规划）

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

5
2 0 1 1 1

输出

4

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
 * 
 * 袋鼠过河（最多跳弹簧的步数） 用 list 来模拟dp数组 list存每一行，横坐标为 各个弹簧的到达情况 未到达为0 到达为1 到达此处陷入为0
 * 
 * @author Dell
 *
 */
public class Main {
    static List<int[]> dp = new ArrayList();
    static int n;
    static int[] is;

    static int f() {
        // 站在第一个弹簧上时
        int step = 0;
        int x = 0;
        int[] s = new int[n + 1];
        for (int j = 0; j < s.length; j++) {
            s[j] = 0;
        }
        s[0] = 1;
        dp.add(s);
        while (step <= n) { // 所有行
            int[] ss = new int[n + 1];// 多出来的最后一位表示岸上
            for (int j = 0; j < ss.length; j++) {
                ss[j] = 0;
            }
            // 每一行 根据本行填写下一行
            for (int i = step; i < ss.length; i++) { // 多出来的最后一位表示岸上
                // 位置 i已到达
                if (dp.get(dp.size() - 1)[i] == 1) {
                    // 走不同的步数
                    for (int j = 1; j <= is[i]; j++) {
                        // 判断不可超出弹簧范围一个一，下标要多减，若超出则选岸上为1
                        if (i + j <= ss.length-2) { 
                            // 在范围内 新位置 不是0 不会陷 访问
                            if (is[i + j] > 0) {
                                ss[i + j] = 1;
                            }
                        } else {
                            // 超出则选最后一个为1
                            ss[ss.length - 1] = 1;
                        }
                }
                }
            }
            dp.add(ss);

            step++;
            if (dp.get(dp.size()-1)[ss.length - 1] == 1) { // 岸上访问到
                return step;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        is = new int[n];
        for (int i = 0; i < is.length; i++) {
            is[i] = sc.nextInt();
        }
        int res = f();
        System.out.println(res);
    }
}