求解整数惩罚值
难度：中等
主题：数学，递归
给定正整数 n，返回 1 到 n 的惩罚值之和。
惩罚值定义为所有整数 i 的平方和，其中 i 的十进制表示可以分割成连续的子串，且这些子串的数值之和等于 i。
示例 1：
输入：n = 10 输出：182 说明：在 [1, 10] 范围内，满足条件的整数 i 有： 1，因为 11 = 1 9，因为 99 = 81，81 可以分割成 8 和 1，8 + 1 = 9 10，因为 10*10 = 100，100 可以分割成 10 和 0，10 + 0 = 10。 因此，10 的惩罚值是 1 + 81 + 100 = 182
示例 2：
输入：n = 37 输出：1478 说明：在 [1, 37] 范围内，满足条件的整数 i 有： 1，因为 11 = 1 9，因为 99 = 81，81 可以分割成 8 和 1，8 + 1 = 9 10，因为 1010 = 100，100 可以分割成 10 和 0，10 + 0 = 10。 36，因为 3636 = 1296，1296 可以分割成 1, 29, 6，1 + 29 + 6 = 36。 因此，37 的惩罚值是 1 + 81 + 100 + 1296 = 1478
约束：
1 ≤ n ≤ 1000
提示：
可以使用递归算法，将数字分割成多个部分，递归地生成每个部分的所有可能分割，然后组合所有可能的分割方式。
解决方案：
我们需要计算给定整数 n 的“惩罚值”。惩罚值定义为所有整数 i (1 ≤ i ≤ n) 的平方和，其中 i 的十进制表示可以分割成连续的子串，这些子串的数值之和等于 i。
方法：
- 遍历每个整数 i 从 1 到 n： 对于每个整数，计算其平方并将其转换为字符串。
- 检查平方是否可分割： 对于每个整数 i，检查其平方的字符串表示是否可以分割成连续的子串，使得这些子串的数值之和等于 i。这个检查使用递归辅助函数完成。
- 递归辅助函数： 这个函数尝试将平方的字符串表示分割成所有可能的连续部分，检查这些部分的数值之和是否等于 i。如果找到有效的分割，则将整数的平方添加到总和中。
让我们用 PHP 实现这个解决方案：
<code class="php"><?php
/**
* @param Integer $n
* @return Integer
*/
function punishmentNumber($n) {
$totalPunishment = 0;
for ($i = 1; $i <= $n; $i++) {
$square = $i * $i;
$squareStr = (string)$square;
if (canSplit($squareStr, $i, 0, 0)) {
$totalPunishment += $square;
}
}
return $totalPunishment;
}
/**
* @param $s
* @param $target
* @param $index
* @param $currentSum
* @return bool
*/
function canSplit($s, $target, $index, $currentSum) {
if ($index === strlen($s)) {
return $currentSum === $target;
}
for ($i = $index; $i < strlen($s); $i++) {
$num = substr($s, $index, $i - $index + 1);
$newSum = $currentSum + (int)$num;
if ($newSum > $target) {
break; // Early termination
}
if (canSplit($s, $target, $i + 1, $newSum)) {
return true;
}
}
return false;
}
// Example Test Cases
echo punishmentNumber(10) . "\n"; // Output: 182
echo punishmentNumber(37) . "\n"; // Output: 1478
?></code>
解释：
- 主循环: 主循环遍历每个整数 i 从 1 到 n。对于每个整数，它计算其平方并将其转换为字符串。
-
递归检查:
canSplit函数是一个递归辅助函数，它检查平方的字符串表示是否可以分割成连续的子串，这些子串的数值之和等于 i。它从字符串的开头开始，尝试所有可能的分割，检查任何分割的组合是否结果之和等于 i。 - 提前终止: 如果添加字符串的一部分超过目标总和 i，循环会提前终止以避免不必要的计算。
- 总和计算: 如果为整数 i 找到有效的分割，则将它的平方添加到总惩罚值中。
这种方法有效地使用递归检查所有可能的分割，确保我们只考虑有效的分割和总和计算，从而得到正确的结果。
