题解 | #牛牛恨66#

算法思想一：递归

解题思路：

由题知：对于 i 位数的答案，是与 i-1 位和 i-2 位的答案有关系的，首先想到采用递归的方式进行计算

1、递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。
2、递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6，那么i-1位必须不选择6（共9种选择），此时可由i-2层得到i层，共9*dfs(i-2)种情况；如果不选择6，那么直接由i-1层得到i层，共9*dfs(i-1)种情况。
3、每一层返回值：返回当前层可能数(dfs(i-2)+dfs(i-1))*9。
注：由于普通递归，会有很多重复计算的情况，可以用一个记忆数组记录之前计算过的情况。

代码展示：

JAVA版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    //声明记忆数组
    long[] memo;
    
    public String calculate (int n) {
        // write code here
        //初始化记忆数组
        memo=new long[n+1];
        //递归
        dfs(n);
        //转化为String
        return String.valueOf(memo[n]);
    }
    private long dfs(int i){
        //终止条件1
        if(i==0){
            memo[i]=1;
            return 1;
        }
        //终止条件2
        if(i==1){
            memo[i]=10;
            return 10;
        }
        if(memo[i]!=0) return memo[i];
        memo[i]=(dfs(i-2)+dfs(i-1))*9;
        //返回当前层状态
        return (dfs(i-2)+dfs(i-1))*9;
    }
}

复杂度分析

时间复杂度 $O(N)$ ：N表示位数，递归遍历N次时间

空间复杂的 $O(N)$ ：需要额外大小为n+1的记忆化数组 $O(N)$ ，递归调用栈空间 $O(N)$ ，所以空间复杂度为 $O(N)$

算法思想二：动态规划

解题思路：

方法一可知：对于 i 位数的答案，是与 i-1 位和 i-2 位的答案有关系的，因此可以采用动态规划来解答

1、状态定义：dp[i]表示输入 i 为i时，有多少个数字不含有连续的6。
2、状态初始化：当输入为0时，只有1不含66，赋值为1；当输入为1时，1到10这十个数都不含66，赋值为10。
3、状态转移：当前位可以选择6，也可以不选择6。如果选择6，那么i-1位必须不选择6（共9种选择），此时可由dp[i-2]进行计算，共9*dp[i-2]种情况；如果不选择6，那么直接由dp[i-1]进行计算，共9*dp[i-1]种情况。综合考虑，dp[i]=(dp[i-2]+dp[i-1])*9。
图解：

代码展示：

Python版本

class Solution:
    def calculate(self , n ):
        # write code here
        # 定义dp数组
        dp = [0] * (n+1)
        # 初始化
        dp[0] = 1
        dp[1] = 10
        # 循环计算
        for i in range(2, n+1):
            # 动态转移方程 
            dp[i] = (dp[i-2] + dp[i-1]) * 9
        # 转换为字符串
        return str(dp[n])

复杂度分析

时间复杂度 $O(N)$ ：N表示位数，循环时间 $O(N)$

空间复杂的 $O(N)$ ：dp数组占用空间