蓝桥杯算法训练-K好数-题解（C++代码）

解题思路:利用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;

}