與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解決方案的步驟，並重復您在此過程中所做的選擇。