如何在簡單動態編程概率中跟蹤路徑？

Question

我想解決一個簡單的DP問題：

給定一個正整數n，您可以執行以下3個步驟中的任何一個。 1）從中減去1。
2）如果它是被2整除，除以2
3）如果它是被3整除，除以3
請找到的步驟的最小數目取n設置爲1，並打印出的步驟。如果有多個解決方案以相同步驟達到目標，請打印出所有這些解決方案。 （如果很難，至少要打印出其中一種解決方案）。

---

獲得最小步數並不難。簡單地應用這樣的自下而上的DP解決方案：

public int getMinSteps(int n) { 
int[] dp = new int[n+1]; 

int i; 
dp[1] = 0; 

for(i = 2 ; i < = n ; i ++) { 
dp[i] = 1 + dp[i-1]; 
if(i%2==0) dp[i] = min(dp[i] , 1+ dp[i/2]); 
if(i%3==0) dp[i] = min(dp[i] , 1+ dp[i/3]); 
} 
return dp[n]; 
} 

但是，我無法解決打印路徑部分。在很高的層面上，我認爲我需要停止每個層面的「行動」，而最低限度是由此決定的？

希望我能在這裏得到一些很好的建議或解決方案。

謝謝！

Answer 1

只要得到另一場來存儲最佳步驟，即-1，/ 2，或/ 3，如果是最佳得到最小路徑中，可能只使用1，2，3作爲指標。

例如，您正在比較a = 1 + dp[i-1],b = 1 + dp[i/2],c = 1 + dp[i/3]。如果a最小，那麼你知道你應該爲-1。將步驟存儲爲1。後來，你只要跳到領域i-1找到下一步直到你到達起點，即1

---

更新：

如果你想打印所有的路徑，你必須存儲所有最佳步驟，並打印所有組合。

具體而言，如果任何最佳路徑經過特定數字，則可以使用-1，/ 2，/ 3的三個布爾字段來存儲。之後，您可以遞歸地打印所有組合，例如遍歷一棵樹。

int[] dp; // for minimum steps 
bool[] gominus1; 
bool[] godivideby2; 
bool[] godivideby3; 
List<Integer> steps; 

PrintAllPath(int n) { 
    if(n == 1) { 
     // print steps 
     return; 
    } 
    steps.push_back(n); 
    if(gominus1[n]) { 
     PrintAllPath(n - 1); 
    } 
    if(godivideby2[n]) { 
     PrintAllPath(n/2); 
    } 
    if(govidivideby3[n]) { 
     PrintAllPath(n/3); 
    } 
    steps.pop_back(); 
} 

Answer 2

這裏是你如何檢索路徑：

public static int getMinSteps(int n) { 
    int[] dp = new int[n + 1]; 
    String[] path = new String[n+1]; 
    int i; 
    dp[1] = 0; 
    path[1] = "end"; 

    for (i = 2; i <= n; i++) { 
     dp[i] = 1 + dp[i - 1]; 
     if (i % 2 == 0) { 

      if(dp[i] < 1 + dp[i/2]){ 
       path[i] = "sub 1," + path[i-1]; 
      } 
      else { 
       path[i] = "div by 2," + path[i/2]; 
      } 

      dp[i] = min(dp[i], 1 + dp[i/2]); 

     } 

     if (i % 3 == 0) { 

      if(dp[i] < 1 + dp[i/3]){ 
       path[i] = "sub 1," + path[i-1]; 
      } 
      else { 
       path[i] = "div by 3," + path[i/3]; 
      } 

      dp[i] = min(dp[i], 1 + dp[i/3]); 
     } 

     if(i % 3 != 0 && i % 2 != 0) { 
      path[i] = "sub 1," + path[i-1]; 
     } 

    } 
    System.out.println("number of steps = "+dp[n]+",path = "+path[n]); 
    return dp[n]; 
} 

這是打印單一路徑。要打印所有你需要的路徑來跟蹤dp [i]的所有可能的最小途徑。所以你需要一個String的二維數組來存儲它們。