解题思路:利用DP(动态规划算法)来简化算法的时间复杂度
注意事项:dp[0][0~n]为0到n的所有可能分支(代表了2位数的所有K好数可能性,包括0,树的层数是两层),dp[1][0~n]为0到n的(代表了3位数的所有K好数可能性,包括0,树的层数是3层),然后dp[0][0~n]这一行重复利用.
参考代码:
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
void K()
{
int n,l,sum=0;
cin>>n>>l;
l--;
ll dp[2][n];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
if(i==0||i==n-1)
dp[0][i]=n-1;
else
dp[0][i]=n-2;
}
for(int k=1;k<l;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(j==0)
dp[k&1][i]=0;
if(j!=i-1&&j!=i+1)
{
dp[k&1][i]+=dp[~k&1][j]%1000000007;
}
}
}
}
for(int i=1;i<n;i++)
{
sum+=dp[~l&1][i]%1000000007;
sum=sum%1000000007;
}
cout<<sum%1000000007<<endl;
}
int main()
{
K();
return 0;
}
0.0分
1 人评分