房间安排

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int p = Integer.parseInt(params[1]);
        // dp[i][j][0]和dp[i][j][1]表示0~i号房间在第i号未房间分配出去和分配出去给j个客人的方案数
        int[][][] dp = new int[n][p + 1][2];
        dp[0][0][0] = 1;   // 0号房间不分配给客人有一种方案
        dp[0][1][1] = 1;   // 0号房间分配给一个客人有一种方案
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= p; j++){
                // 第i号房间不分配给第j个客人，第i-1号房间分没分配给他都有可能
                dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % 10000;
                // 第i号房间要分配给第j个客人，那第i-1号房间肯定不能分配给上一个客人
                dp[i][j][1] = j > 0? dp[i - 1][j - 1][0]: 0;
            }
        }
        System.out.println((dp[n - 1][p][0] + dp[n - 1][p][1]) % 10000);
    }
}

1. 当第i个房间选择选择了住人 ，那么剩下的客人(j - 1)应该从第i + 2间房开始住
2. 当第i个房间选择了不住人，那么需要住的客人还是j，且应该从第i + 1间房开始住

import java.io.BufferedReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        br.close();
        int n = Integer.parseInt(params[0]);
        int p = Integer.parseInt(params[1]);
        // 从第i间房到n - 1间房住j人的方案数
        int[][] dp = new int[n + 2][p + 1];
        // 初始化，不住人(j = 1)也是一种方案
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = n - 1; i >= 0; i--) {
            // j从1开始，为0的情况已经包含在初始化内
            for (int j = 1; j <= p; j++) {
                // 第i个住人   + dp[i + 2][j - 1]
                // 第i个不住人  + dp[i + 1][j]
                dp[i][j] = (dp[i + 2][j - 1] + dp[i + 1][j]) % 10000;
            }
        }
        System.out.println(dp[0][p]);
    }
}