题解 | #牛牛恨66#

题意整理

• 输入正整数 。
• 在 到 之间，有多少个数字不包含连续的 ，则输出多少。

方法一（记忆化递归）

1.解题思路

• 递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。
• 递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6，那么i-1位必须不选择6（共9种选择），此时可由i-2层得到i层，共 种情况；如果不选择6，那么直接由i-1层得到i层，共 种情况。
• 每一层返回值：返回当前层可能数 。

由于普通递归，会有很多重复计算的情况，可以用一个记忆数组记录之前计算过的情况。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    //声明记忆数组
    long[] memo;

    public String calculate (int n) {
        //初始化记忆数组
        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;
    }
}

3.复杂度分析

• 时间复杂度：最多递归n次，所以时间复杂度是 。
• 空间复杂度：需要额外大小为n+1的记忆化数组，所以空间复杂度为 。

方法二（动态规划）

1.解题思路

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

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    public String calculate (int n) {
        //定义dp数组
        long[] dp=new long[n+1];
        //赋初始
        dp[0]=1;
        dp[1]=10;
        //根据状态转移方程，确定所有的状态
        for(int i=2;i<=n;i++){
            dp[i]=(dp[i-2]+dp[i-1])*9;
        }
        //转化为字符串
        return String.valueOf(dp[n]);
    }
}

3.复杂度分析

• 时间复杂度：循环体总共执行n-1次，所以时间复杂度是 。
• 空间复杂度：需要额外大小为n+1的dp数组，所以空间复杂度为 。