Day10力扣打卡

Day10力扣打卡

打卡记录

求一个整数的惩罚数（预处理+递归）

链接

int PRE_SUM[1001];int init = []() {for (int i = 1; i <= 1000; i++) {string s = to_string(i * i);int n = s.length();function<bool(int, int)> dfs = [&](int p, int sum) -> bool {if (p == n) { // 递归终点return sum == i; // i 符合要求}int x = 0;for (int j = p; j < n; j++) { // 枚举分割出从 s[p] 到 s[j] 的子串x = x * 10 + s[j] - '0'; // 子串对应的整数值if (dfs(j + 1, sum + x)) {return true;}}return false;};PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(0, 0) ? i * i : 0);}return 0;
}();class Solution {
public:int punishmentNumber(int n) {return PRE_SUM[n];}
};