题解：. - 力扣（LeetCode）. - 力扣（LeetCode）

数位 DP 通用模板_哔哩哔哩_bilibili

class Solution {
public:int numberOf2sInRange(int n) {std::string str = to_string(n);int len = str.size();std::vector<std::vector<int>> memo(len, std::vector<int>(len, -1));int begin = 0;// is_limit表示当前每个位置是否是按照n对应位置去，往下走的bool is_limit = true;// 表示当前是否为一个数字, 前导0的情况就不是一个数字bool is_num = false;// 记录出现2的次数int count = 0;return dfs(str, begin, is_num, is_limit, count, memo);}
private:int dfs(std::string& str, int begin, bool is_num, bool is_limit, int count,std::vector<std::vector<int>>& memo) {// 已经走动末尾if (begin >= str.size()) {// 是一个数字if (is_num) {return count;}return 0;}// 记忆话搜素if (!is_limit && is_num && memo[begin][count] != -1) {return memo[begin][count];}int result = 0;if (!is_num) {// 不是数字，可以选择跳过，is_limit就没有限制了, is_num也不是一个数字result += dfs(str, begin+1, false, false, count, memo);}// 判断当前位置可以选择数字的最大值// 如果被限制了，就只能是当前str位置的元素，没限制就是9int up = is_limit ? str[begin] - '0' : 9;for (int i = 1 - is_num; i <= up; ++i) {// 往下递归，且记录信息result += dfs(str, begin+1, true, is_limit && (i == up ? true : false),count + (i == 2 ? 1 : 0), memo);}// 更新记忆话,当前位置，前门出现了2的个数count个，后面可能的情况if (!is_limit) {memo[begin][count] = result;}// 返回return result;}
};