这一段代码为什么不能求解出[0~n不包含4的数的个数呢: int dfs(int len, bool ismax) { // ismax为数位上界变量 if(len == 0) return 1; if(!ismax && dp[len] != -1) return dp[len]; int ans = 0, maxx = ismax ? digit[len] : 9; for(int i = 0; i <= len; i++) { if(i == 4) continue; //if(pre == 6 && i == 2) continue; ans += dfs(len - 1, ismax && i == maxx); } if(!ismax) dp[len] = ans; return ans; }
时间: 2024-04-19 11:24:25 浏览: 16
这段代码是一个递归函数 `dfs`,用于计算不包含数字 4 的数的个数。
代码中的 `dfs` 函数接受两个参数:`len` 表示当前数位的位置,`ismax` 表示当前数位是否达到上界。
首先,递归终止条件是当 `len` 等于 0 时,表示已经处理完所有数位,可以返回 1。
然后,在递归过程中,首先判断是否需要使用已经计算过的结果。如果 `ismax` 为假且 `dp[len]` 不等于 -1,则说明之前已经计算过当前数位的结果,可以直接返回结果。
接下来,定义变量 `ans` 用于记录满足条件的数字个数,以及变量 `maxx` 表示当前数位的上界。如果 `ismax` 为真,则 `maxx` 等于当前数位 `digit[len]`,否则 `maxx` 等于 9。
然后,使用循环从 0 到 `len` 遍历所有可能的取值 `i`。在每次循环中,判断如果 `i` 等于 4,则跳过当前循环,排除数字 4。然后,递归调用 `dfs` 函数,传入 `len - 1` 和 `ismax && i == maxx` 作为参数,并将返回的结果累加到 `ans` 中。
最后,如果 `ismax` 为假,则将结果 `ans` 存入 `dp[len]`,以备之后的计算使用,并返回 `ans`。
这段代码通过递归的方式,不断地将问题规模缩小,直到达到终止条件。在每一层递归中,通过判断条件来决定是否进一步递归,并将结果累加到最终的答案中。在需要时,利用 `dp` 数组保存已经计算过的结果,以避免重复计算,提高效率。
要计算 [0~n) 区间内不包含数字 4 的数的个数,可以调用 `dfs(n, true)`。其中,`n` 是区间的上界,`true` 表示达到上界。
注意,这段代码中有一处注释掉的判断语句 `//if(pre == 6 && i == 2) continue;`。如果需要排除以 62 开头的数字,可以取消注释该语句,并在每次递归调用 `dfs` 时传入 `i` 作为前一位数字的参数。