找到最小整数,其数字平方和将添加到给定数字

Question

例:

输入:| 输出:

• 5 - > 12(1 ^ 2 + 2 ^ 2 = 5)

• 500 - > 18888999(1 ^ 2 + 8 ^ 2 + 8 ^ 2 + 8 ^ 2 + 9 ^ 2 + 9 ^ 2 + 9 ^ 2 = 500)

我写了一个非常简单的暴力解决方案,但它有很大的性能问题:

#include <iostream>
using namespace std;

int main() {
 int n;
 bool found = true;
 unsigned long int sum = 0;

 cin >> n;
 int i = 0;
 while (found) {
     ++i;
     if (n == 0) { //The code below doesn't work if n = 0, so we assign value to sum right away (in case n = 0)
         sum = 0;
         break;
     }
     int j = i;
     while (j != 0) { //After each iteration, j's last digit gets stripped away (j /= 10), so we want to stop right when j becomes 0
         sum += (j % 10) * (j % 10); //After each iteration, sum gets increased by *(last digit of j)^2*. (j % 10) gets the last digit of j
         j /= 10;
     }
     if (sum == n) { //If we meet our problem's requirements, so that sum of j's each digit squared is equal to the given number n, loop breaks and we get our result
        break;
     }
     sum = 0; //Otherwise, sum gets nullified and the loops starts over
 }

 cout << i;

 return 0;
 }

我正在寻找一个快速解决问题的方法.

Answer 1

使用动态编程.如果我们知道最优解的第一个数字,那么其余的将是剩余总和的最优解.因此,我们可以猜测第一个数字并对较小的目标使用缓存计算以获得最佳数据.

def digitsum(n):
    best = [0]
    for i in range(1, n+1):
        best.append(min(int(str(d) + str(best[i - d**2]).strip('0'))
                        for d in range(1, 10)
                        if i >= d**2))
    return best[n]