算法训练 K好数

import java.util.Scanner;

public class Main {
    static int[][] dp;
    /*
     * dp[i][j]代表i位数中以j为首的k好数的个数
     * dp[i][0]全为1
     * 一般的j,p, 当p != j-1 && p != j+1
     * 那么dp[i][j] += dp[i-1][p]
     * 即i位数中以j为首的k好数的个数等于i-1位数中以不与j相邻的数为首的k好数的个数的和
     */
    static long MOD = 1000000007;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int l = in.nextInt();
        int sum = 0;
        dp = new int[l][k];
        for ( int i = 1 ; i < k ; i++){
            dp[0][i] = 1;
        }

        for ( int i = 1 ; i < l ; i++){
            for ( int j = 0 ; j < k ; j++){
                for ( int p = 0 ; p < k ; p++){
                    if ( p != j-1 && p != j+1){
                        dp[i][j] += dp[i-1][p];
                        dp[i][j] %= MOD;
                    }
                }
            }
        }

        for ( int i = 0 ; i < k ; i++){
            sum += dp[l-1][i];
            sum %= MOD;
        }
        System.out.print(sum);
        in.close();
    }

}