题解 | #牛牛恨66#

题目描述
众所周知，牛牛不喜欢6这个数字（因为牛牛和66发音相近）
所以他想知道，不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）
输入只包含一个正整数n（1<=n<20）

方法一：递归的思想

求解思路
对于本题目所要求解的答案，因为要求出不连续的6，因此我们自然想到第i位数字是否为6与i-1和i-2这两位是否为6有关，因此我们可以用递归的方法求出相应的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    long[] memory; // 辅助数组
    public String calculate (int n)
    {
        memory=new long[n+1]; // 初始化辅助数组
        dfs(n); // 递归
        return String.valueOf(memory[n]);
    }
    private long dfs(int i)
    {   // stop 1
        if(i==0)
        {
            memory[i]=1;
            return 1;
        }
        // stop 2
        if(i==1)
        {
            memory[i]=10;
            return 10;
        }
        if(memory[i]!=0) 
            return memory[i];
        memory[i]=(dfs(i-2)+dfs(i-1))*9;
        return (dfs(i-2)+dfs(i-1))*9; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入辅助数组，使用额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：动态规划的思想求解

求解思路
基于方法一，我们知道对于第i位是否为6，与第i-1和i-2位数字有关，因此我们定义dp[i]表示第i位填入数字以后，有多少种结果使得不存在连续的6，其状态转移方程为： $dp[i] = (dp[i-2] + dp[i-1]) * 9$ 。同时我们定义初始化条件，当输入为0时，dp[0]=1.当输入为1时，dp[1]=10。根据上述的思路，我们即可用动态规划的思想对本题进行答案的求解。

图片说明

解题代码

class Solution:
    def calculate(self , n ):
        # 定义mydp数组
        mydp = [0] * (n+1)
        # 初始化
        mydp[0] = 1
        mydp[1] = 10
        # 循环计算
        for i in range(2, n+1):
            mydp[i] = (mydp[i-2] + mydp[i-1]) * 9 # 动态规划的思想
        return str(mydp[n]) # 返回结果

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入dp[n]数组，使用额外的内存地址空间，因此空间复杂度为 $O(N)$