题目链接

https://www.dotcpp.com/oj/problem2223.html

解题思路

真没想到自己做出来了.
dp[i][j]表示第i位数(从低位到高位),当前位为j的可能.
除了最高位,其他位的每个j都等于前面一位(i-1)与之不相邻数j的和.
最高位的0对应的dp为0,其他的同上.
最后累加求和.

AC代码

#include<bits/stdc++.h>
#define ll long long
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
using namespace std;
const int mod=1000000007;
const int N=105;
ll sum,tmp,K,L,dp[N][N],ans;
int main(){    
    sc(K);sc(L);
    for(ll i=0;i<K;i++) dp[1][i]=1;
    tmp=K;
    for(ll i=2;i<=L;i++){
        sum=tmp;
        tmp=0;
        for(ll j=0;j<K;j++)
            dp[i][j]=(sum-(j>=1?dp[i-1][j-1]:0)-(j<K-1?dp[i-1][j+1]:0)+mod)%mod,tmp=(tmp+dp[i][j])%mod;
    }
    for(ll i=1;i<K;i++)
        ans=(ans+dp[L][i])%mod;
    pr(ans);
}