与n相加的平方整数的最小数目 - 如何迭代执行？

Question

我正在尝试查找总和给定数字n的平方整数的最小数目。

我用递归函数解决了它，但我想迭代地完成它。
如何使用一些循环，而不是递归方法？

public static ArrayList<Integer> minLen(int n) 
    { 
     // base case of recursion 
     if (n == 0) 
      return new ArrayList<Integer>(); 

     ArrayList<Integer> best = null; 
     int bestInt = -1; 
     for (int i = 1; i*i <= n; ++i) 
     { 
      // Check what happens if we use i^2 as part of our representation 

      ArrayList<Integer> guess = minLen(n - i*i); 
      System.out.println("i:"+i); 
      System.out.println("Guess"+guess); 
      // If we haven't selected a 'best' yet (best == null) 
      // or if our new guess is better than the current choice (guess.size() < best.size()) 
      // update our choice of best 
      if (best == null || guess.size() < best.size()) 
      { 
       best = guess; 
       System.out.println("best"+best); 

       bestInt = i; 
       System.out.println("bestInt"+bestInt); 
      } 
     } 

     best.add(bestInt); 
     System.out.println("bestInt"+bestInt); 
     System.out.println("best"+best); 
     return best; 
    } 

Answer 1

这可以用动态规划与循环

你要解决的是找到整数的平方即总计为n的最小数量的问题解决了。

它可以Dynamic Programming通过下面的伪代码来解决：

int[] sol = new int[n+1]; 
//init: 
sol[0] = 0; 
for (int i = 1; i <= n; i++) sol[i] = Integer.MAX_VALUE; 
//fill the value for each i in increasing order: 
for (int i =1; i <= n; i++) 
    for (int j = 1; j*j <= i; j++) 
      //make sure sol[i] contains the best possible solution 
      sol[i] = Math.min(sol[i], sol[i-j*j] + 1); 

上面给你的最小可能数（sol[n]是答案），得到平方数自己：

List<Integer> numbers = new ArrayList<>(); 
int curr = n; 
//while we haven't 'exhausted' the number: 
while (curr > 0) { 
    //check all numbers we could have added 
    for (int j=1; j*j <= curr ; j++) { 
     if found the correct number we used: 
     if (sol[curr - j*j] == sol[curr ] - 1) { 
       //add it to the solution, reduce it from curr and repeat 
       numbers.add(j); 
       curr = curr - j*j; 
       break; 
     } 
    } 
} 

这个想法是重复DP解决方案的步骤，并重复您在此过程中所做的选择。