题目描述

要求输出不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）
输入只包含一个正整数n（1<=n<20）

方法一 记忆化搜索

解题思路

定义DFS函数，搜索位十进制数字中符合要求数字的个数。
在计数时，对于位数为的数字，如果第位为，那么第位必须不能为，所以第位有个数字可以选择，也就是说有种情况；如果第位不为，第位有种选择，第位可以随便选取，有种情况。所以，位数字符合要求的数字个数可以通过位和位答案得到，于是可以通过递归/DFS的思路得到答案。

接下来考虑初始情况即可，当输入为时，仅考虑数字，不含有，故应返回.当输入为时，考虑数字，不含有，故应返回。
实际上，上述思路的时间复杂度较高，因为每次求解位数字时，需要重新从头递归各个位数数字的数量，常用的优化方法是添加记忆数组，称为记忆化搜索。因为位数为的数量是固定的，所以用数组存储起来，避免了重复计算。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    // 记忆化搜索数组，num[i]: i位数字中有多少个符合要求的数字
    long num[21] = {0};

    long dfs(int x){
        // 起始情况：0位数字1个符合要求
        if(x==0){
            num[x]=1;
            return 1;
        }
        // 起始情况：1位数字10个符合要求
        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) {
        // 注意返回的是字符串
        return to_string(dfs(n));
    }
};

复杂度分析

• 时间复杂度：需要计算前位数字的个数，因为记忆化手段，每一位只需要计算一次，每次计算时间复杂度为，所以总的时间复杂度为
• 空间复杂度：需要大小的记忆化数组和深度为的递归栈，空间复杂度为

方法二 动态规划

解题思路

实际上提出DP的初衷就是为了解决递归过程中重复计算的问题，所以方法二与方法一思路类似，只是DP倾向于使用迭代的方法，而搜索倾向于使用递归的方法。
定义数组，表示位数字中符合要求数字个数。根据方法一中提出的结论，我们容易得到动态规划的更新方法： 。其中，。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    string calculate(int n) {
        // f[i]: i位数字中有多少个符合要求的数字
        long f[21] = {0, 10, 99};
        for(int i=3;i<20;i++)
                // 根据方程更新动态规划数组
            f[i] = (f[i-1]+f[i-2])*9;
        // 注意返回的是string
        return to_string(f[n]);
    }
};

复杂度分析

• 时间复杂度：需要进行次迭代以得出答案，时间复杂度为
• 空间复杂度：需要大小为的动态规划数组，空间复杂度为

方法三 打表

解题思路

因为，范围较小，所以可以使用打表的方法。先用方法一或者方法二算出结果，然后直接打表输出。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    string ret[20] = {
        "0",
        "10",
        "99",
        "981",
        "9720",
        "96309",
        "954261",
        "9455130",
        "93684519",
        "928256841",
        "9197472240",
        "91131561729",
        "902961305721",
        "8946835807050",
        "88648174014939",
        "878355088397901",
        "8703029361715560",
        "86232460051021149",
        "854419404714630381",
        "8465866782890863770"
    };

    string calculate(int n) {
        return ret[n];
    }
};

复杂度分析

• 时间复杂度：只需要打表输出，时间复杂度为
• 空间复杂度：打表需要大小为的字符串数组，空间复杂度为