题目描述

// 记忆化搜索
public class Main {
    static int[][] cache;
    static int n = 10;
    public static void main(String[] args) {
        cache = new int[n + 1][2];
        System.out.println(dfs(n, 0));
    }
    // dfs，返回从0到pos的方案数目
    public static int dfs(int pos, int backed) {
        if (pos == 0) return 1;
        if (cache[pos][backed] > 0) return cache[pos][backed];
        int sum = 0;
        sum += dfs(pos - 1, backed);
        if (pos - 2 >= 0) {
            sum += dfs(pos - 2, backed);
        }
        if (backed == 0 && pos + 1 <= n) {
            sum += dfs(pos + 1, 1);
        }
        cache[pos][backed] = sum;
        return sum;
    }
}