蓝桥杯 K好数（dp）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 #define Bug cout<<"---------------------"<<endl
18 const int maxm=1e6+10;
19 const int maxn=1e5+10;
20 using namespace std;
21 
22 int dp[105][105];//dp[i][j]，其中i表示总共有多少位(i<=L)，j表示最前面的那个数字（j<K）
23 
24 int main()
25 {
26     int k,l;
27     scanf("%d %d",&k,&l);
28     for(int i=0;i<k;i++)////第1行初始化为1，便于下面for循环i=2时的计算 
29         dp[1][i]=1;
30     for(int i=2;i<=l;i++)
31     {
32         for(int j=0;j<k;j++)
33         {
34             for(int g=0;g<k;g++)
35             {
36                 if(g!=j-1&&g!=j+1)////左右不相邻
37                 {
38                     dp[i][j]+=dp[i-1][g];//循环累加上一行dp
39                     dp[i][j]%=mod;
40                 }    
41             }
42         }
43     }
44     LL ans=0;
45     for(int i=1;i<k;i++)//将最后一行累加，dp[l][0]代表以0开头的数，不统计
46     {
47         ans+=dp[l][i];
48         ans%=mod;
49     }
50     printf("%lld\n",ans);
51     return 0;
52 }