C - Numbering Blocks

問題文：C - Numbering Blocks

解説を見ると全探索か深さ優先探索で解いている人が多く、DPで解いている人があまりいなさそうだったのでメモを残します。

考察

• 以下のイメージです。
• dp[i][j][k]を次で定義する
  • のときの条件を満たす数字の書き込み方の数
• DP遷移
  • dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k] + dp[i][j][k-1]
• 初期値

dp[1][0][0] = 1;
dp[1][1][0] = 1;
dp[1][1][1] = 1;

• の条件に注意

コード*1

int a1 = scan.nextInt();
int a2 = scan.nextInt();
int a3 = scan.nextInt();

int[][][] dp = new int[4][4][4];
dp[1][0][0] = 1;
dp[1][1][0] = 1;
dp[1][1][1] = 1;
for(int i=2; i<4; i++){
    for(int j=0; j<4; j++){
        for(int k=0; k<4; k++){
            if(!(i>=j && j>=k))continue;
            dp[i][j][k] = 
                    (i-1>=j ? dp[i-1][j][k] : 0)
                    + (j-1>=k ? dp[i][j-1][k] : 0)
                    + (k-1>=0 ? dp[i][j][k-1] : 0);
        }
    }
}

System.out.println(dp[a1][a2][a3]); 

フック長公式というキーワードが気になる。調べる。

*1:入出力用のライブラリを使用している