蓝桥杯算法提高VIP-超级玛丽-题解（Java代码）

import java.util.Scanner;

public class 超级玛丽_动规做法 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n + 1];// 记录陷阱的位置
        int[] dp = new int[n + 1];// 记录步数
        if (n >= 2) {
            dp[1] = dp[2] = 1;
        }

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            if (x <= n) {
                a[x] = 1;
                dp[x] = 0;
            }
        }
        for (int i = 3; i <= n; i++) {
            if (a[i] != 1) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
        }
        System.out.println(dp[n]);
    }

}