题解 | #牛牛恨66#

一.题目描述
NC517牛牛恨66
求不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的），输入只包含一个正整数n（1<=n<20）
二.算法(动态规划)
图片说明
状态定义：dp[i]表示输入为i时，有多少个数字不含有连续的6。
状态初始化：当输入为0时，只有1不含66，赋值为1；当输入为1时，1到10这十个数都不含66，赋值为10。
状态转移：对于当前位可以有两种选择一种是选择6，另一种是不选择6。如果选择6，那么i-1位必须不能选择6（10-1=9，共9种选择），此时可由dp[i-2]进行计算，共9dp[i-2]种情况；如果不选择6，那么直接由dp[i-1]进行计算，共9dp[i-1]种情况。综合考虑，dp[i]=(dp[i-2]+dp[i-1])*9。
下面是完整代码：

class Solution {
public:
    string calculate(int n) {
        //注意需要开long long
        long long int dp[25]={0,10,99};
        for(int i=3;i<20;i++){
            dp[i]=(dp[i-1]+dp[i-2])*9;
        }
        return to_string(dp[n]);
    }
};

时间复杂度： $O(n)$ 需要从头开始遍历一遍
空间复杂度： $O(n)$ 需要额外开辟空间来存储dp
优缺点：代码实现相当简单，但是思考过程复杂。
三.算法(记忆化搜索)
当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。当前位（第i位）可以选择6，也可以不选择6。如果选择6，那么i-1位必须不选择6（10-1=9，共9种选择），此时可由i-2层得到i层，共9 * dfs(i-2)种情况；如果不选择6，那么直接由i-1层得到i层，共9*dfs(i-1)种情况。返回当前层可能数9 * (dfs(i-2)+dfs(i-1))。为了提高搜索效率，可以用一个记忆数组记录之前计算过的情况。下面给出完整代码：

class Solution {
public:
    long long int num[25];
    long long int dfs(int x){
        if(x==0){
            num[x]=1;
            return 1;
        }
        if(x==1){
            num[x]=10;
            return 10;
        }
        if(num[x]!=0) return num[x];
        num[x]=dfs(x-1)*9+dfs(x-2)*9;
        return num[x];
    }
    string calculate(int n) {
        //对数组进行初始化
        memset(num,0,sizeof(num));
        long long int sum=dfs(n);
        return to_string(sum);
    }
};

时间复杂度： $O(n)$ ，进行n次递归。
空间复杂度： $O(n)$ ，需要额外空间进行记忆化。
优缺点：思路简单，但是代码实现复杂