编程：跳柱子（网易校招真题）

编程：跳柱子（网易校招真题）

小易有n根柱子，第i根柱子的高度为hi，一开始小易在第一根柱子上，他可以跳到第j根柱子上，hj < hi 且 1 <= j - i <= k。其中k为指定的一个数字。

另外小易拥有一次释放超能力的机会。这次超能力可以使小易跳到任意满足1<= j - i <= k 的柱子j上，柱子的高度没有限制。

现在小易想知道，小易是否能到达第n根柱子。

输入描述：

第一行数据数组T

对于每组数据，第一行数字n, k, 接下来一行n个数字表示hi

1 <= n <= 1000, 1 <= hi <= 10^9, 1 <= T <= 10, 1 <= k <= n

输出描述：

能跳到第n根柱子输出"YES"，不能跳到第n根柱子就输出"NO".

输入例子1:

1
5 3
6 2 4 3 8

输出例子1:

YES

输入例子2:

1
5 2
1 8 2 3 4

输出例子2:

NO

解题思路：

一开始，想的是采用DFS，每到达一根柱子就对它前面的k根柱子进行DFS遍历，在遍历的过程中可以使用一次超能力，当能够到达第n根柱子就说明这种跳法是可行的，返回true.

但是，时间复杂度太高，OJ无法通过。（可以使用memo来记录搜索过的路径，但我试过，不知该如何做，欢迎大佬赐教）。

采用动态规划（Dynamic Programming）

动态规划通常需要两步

1. 设dp[i]表示能否从第一根柱子到达第i根柱子：

• dp[i]初始化为-1；
• dp[i]=0表示不能到达；
• dp[i]=1表示能到达，并且不使用超能力；
• dp[i]=2表示能到达，并且使用了超能力

2. 状态转移方程
   
3. 在使用超能力到达 i 的时候分为：
   • 前面没有使用过超能力到达了 j ，这次使用超能力就能从 j 到达 i ;
   • 前面已经使用了超能力到达 j，这次不能再使用超能力了，要想到达 i ，就必须满足 h[j] >= h[i]

代码如下：
Java

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        int n, k;
        for (int i = 0; i < T; i++) {
            n = input.nextInt();
            k = input.nextInt();
            int[] h = new int[n];
            int[] dp = new int[n];
            for (int j = 0; j < n; j++) {
                h[j] = input.nextInt();
                dp[j] = -1;
            }
            int s = 1; //超能力可以使用1次
            dp[0] = 1;
            boolean res = helper(h, dp, k, s);
            if (res) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    public static boolean helper(int[] h, int[] dp, int k, int s) {
        for (int i = 1; i < dp.length; i++) {
            // 不用超能力到达j
            for (int j = i - 1; j >= i - k && j >= 0; j--) {
                if (dp[j] == 1 && h[j] >= h[i]) { //前面不用超能力到达j，不用超能力，能从j到达i
                    dp[i] = 1;
                    break;
                }
            }
            if (dp[i] == 1) continue;
            for (int j = i - 1; j >= i - k && j >= 0; j--) {
                if (s > 0 && dp[j] == 1 && h[j] < h[i]) { //不用超能力到达j，再用超能力从j到达i
                    dp[i] = 2;
                    break;
                }
                else if (dp[j] == 2 && h[j] >= h[i]) { //用超能力达到j，再直接从j到达i
                    dp[i] = 2;
                    break;
                }
            }
            if (dp[i] == -1) dp[i] = 0; //不能直接到达 且 不能使用超能力到达，则该点就不可到达
        }
        return (dp[dp.length - 1] == 1 || dp[dp.length - 1] == 2);
    }
}

C++

#include <cstdio>
#include <vector>
using namespace std;

bool helper(vector<int>& h, int n, vector<int>& dp, int k, int s) {
    for (int i = 1; i < n; i++) {
        // 不用超能力到达 j
        for (int j = i - 1; j >= i - k && j >= 0; j--) {
            if (dp[j] == 1 && h[j] >= h[i]) {
                dp[i] = 1;
                break;
            }
        }
        if (dp[i] == 1) continue;
        for (int j = i - 1; j >= i - k && j >= 0; j--) {
            if (s > 0 && dp[j] == 1 && h[j] < h[i]) { // 不使用超能力到达 j, 再使用超能力从 j 到达 i
                dp[i] = 2;
                break;
            }
            else if (dp[j] == 2 && h[j] >= h[i]) { // 使用超能力到达 j，不使用超能力从 j 到达 i
                dp[i] = 2;
                break;
            }
        }
        if (dp[i] == -1) { // 上诉两种情况都不满足则说明不能到达 i
            dp[i] = 0;
        }
    }
    return (dp[n - 1] == 1 || dp[n - 1] == 2);
}

int main() {
    int T, n, k;
    scanf("%d", &T);
    vector<int> h;
    for (int i = 0; i < T; i++) {
        scanf("%d %d", &n, &k);
        vector<int> dp(n, -1);
        h.clear();
        for (int j = 0; j < n; j++) {
            int num;
            scanf("%d", &num);
            h.push_back(num);
        }
        dp[0] = 1;
        bool res = helper(h, n, dp, k, 1);
        if (res) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}