實現原始計算器的動態編程解決方案

Question

這是Coursera算法工具箱課程中的一個問題。問題說明如下：

，你被賦能與當前數量 X執行以下三個操作的原語計算器：乘以2的x，乘以3 x或添加1到x。你的目標被賦予一個正整數n，發現獲取從1

我實現了一個遞歸解決方案，並使用記憶化數起數n所需的操作 最小數量，並設法解決一些測試用例，但我一直在失敗（他們不告訴我哪個輸入失敗）。

這裏是我的解決方案： https://codeshare.io/aYWoPL

我不知道，爲什麼像預想的那樣我的代碼不能正常工作。我不希望你給我代碼，我可以在網上找到如果我想要的，我只是想知道爲什麼我的代碼不工作！提前致謝。

我搜索了以前的問題，但沒有找到令人滿意的解決方案，所以對不起，如果這是你們中的一些人的重複。

Answer 1

不知道爲什麼你有特殊情況n == 10，以及重複的語句。但真正嚴重的錯誤是使用else if - 一個數字可以是的倍數3和2。你需要採取必要的所有三個操作的最基本的步驟：

long long numOp (int n, long long num_operations[]) { 
    if (n <= 1) return 0; 

    if (num_operations[n - 2] > 0) 
     return num_operations[n - 2]; 

    long long min = numOp(n - 1, num_operations); 
    if (n % 3 == 0) { 
     long long temp = numOp(n/3, num_operations); 
     if (temp < min) min = temp; 
    } 
    if (n % 2 == 0) { 
     long long temp = numOp(n/2, num_operations); 
     if (temp < min) min = temp; 
    } 

    return (num_operations[n - 2] = 1 + min); 
}