算法题3.小Q爬塔

题目描述:

小Q正在攀登一座宝塔，这座宝塔很特别，塔总共有n层，但是每两层之间的净高却不相同，所以造成了小Q爬过每层的时间也不同。如果某一层的高度为x，那么爬过这一层所需的时间也是x， 小Q还会使用一种魔法，每用一次可以让他向上跳一层或两层，但是每次跳跃后小Q都将用完魔法力，必须爬过至少一层才能再次跳跃（你可以认为小Q需要跳两次一层才休息，最后也可以跳到塔外，即超过塔高，跳是不需要消耗时间的）
小Q想用最短的事件爬到塔顶，希望你能告诉他最短时间是多少

输入描述
第一行一个数n(n <= 10000)，表示从下往上每层的高度。
输出描述
一个数，表示最短时间

输入样例：

5 
3 
5 
1 
8 
4

输出样例

1

解题思路

• p[i]表示到达第i层的最短时间，并且到达第i层的方式是爬
• t[i]表示到达第i层的最短时间，并且到达第i层的方式是跳

到达第i层的方式是爬还是跳。

• 情况1 -- 到达第i层的方法是爬：
  那么到达第i-1层的方法可以是爬也可以是跳，从两者中选最小。
  p[i] = min(p[i - 1], t[i - 1]) + a[i];
• 情况2 -- 到达第i层的方式是跳：
  那么可以从第i-1层起跳，也可以从i-2层起跳。
  并且到达第i-1层和i-2层的方式只能是爬（到第i层是跳），所以在两者中选最小。
  t[i] = min(p[i - 1], p[i - 2]);
  最后在p[n]和t[n]中选最小者做结果
  也就是说跳是不记时间的，只有爬需要时间 = =，看了半天跟着调试了一遍才想明白。

示例解题代码：

/**
 * 算法：动态规划
 * 解题思路：
 * p[i]表示到达第i层的最短时间，并且到达第i层的方式是爬
 * t[i]表示到达第i层的最短时间，并且到达第i层的方式是跳
 * 到达第i层的方式是爬还是跳。
 *     情况1 -- 到达第i层的方法是爬：
 *            那么到达第i-1层的方法可以是爬也可以是跳，从两者中选最小。
 *                p[i] = min(p[i - 1], t[i - 1]) + a[i];
 *     情况2 -- 到达第i层的方式是跳：
 *            那么可以从第i-1层起跳，也可以从i-2层起跳。
 *            并且到达第i-1层和i-2层的方式只能是爬（到第i层是跳），所以在两者中选最小。
 *               t[i] = min(p[i - 1], p[i - 2]);
 *  最后在p[n]和t[n]中选最小者做结果
 */
public static void main(String[] args)
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    int x;
    //p[i]表示到达第i层的最短时间，并且到达第i层的方式是爬
    int[] p = new int[n + 1];
    //t[i]表示到达第i层的最短时间，并且到达第i层的方式是跳
    int[] t = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        x = scanner.nextInt();
        p[i] = min(p[i - 1], t[i - 1]) + x;
        if (i == 1) continue;
        t[i] = min(p[i - 1], p[i - 2]);
    }
    scanner.close();

    System.out.println(min(p[n], t[n]));
}

private static int min(int a, int b) {
    return a > b ? b : a;
}