はなぜ322コインの変更をleetcodeする私の解決策はここ

Question

をタイムアウトない私のコードです：

class Solution { 
    std::unordered_map<int, int> um; 
public: 
    int coinChange(vector<int>& coins, int amount) { 
     if (amount == 0) 
      return 0; 

     auto it = um.find(amount); 
     if (it != um.end()) 
      return it->second; 

     int ret = -1; 

     for (int c : coins) 
     { 
      int n = 1; 
      while (true) 
      { 
       int a = amount - n * c, m = 0; 
       if (a < 0) 
        break; 
       if (a > 0) 
        m = coinChange(coins, a); 
       if (m != -1) 
       { 
        if (ret == -1) 
         ret = m + n; 
        else 
         ret = std::min(ret, m + n); 
       } 
       n++; 
      } 
     } 

     um[amount] = ret; 
     return ret; 
    } 
}; 

私の知る限り、それはほとんどのupvotedソリューションに非常に似ている、それも同じハッシュテーブルを構築します。しかし、私は任意の入力でタイムアウトを取得します。 私はローカルでエラーを見つけることができません。

何が間違っている可能性がありますか？

編集：

私は、問題文を含める：

あなたが異なる宗派や金額の合計額のコインを与えられています。その額を補うために必要なコインの数を計算する関数を書く。コインの組み合わせによってその金額を補うことができない場合は、-1を返します。

例： コイン= [1、2、5]、量= 11 リターン3（11 = 5 + 5 + 1）

アプローチ：

使用動的プログラミング（再帰+メモ化）。ある金額の場合は、金額がプラスである限りすべてのコインを試してください。上記の例の場合：

S(11) = 1 + S(10) | 2 + S(9) | 3 + S(8) | ... | 11 + S(0) | //try coin 1 

     1 + S(9) | 2 + S(7) | 3 + S(5) | ... | 5 + S(1) | //try coin 2 

     1 + S(6) | 2 + S(1) //try coin 5 

恩赦この質問の周りの混乱は、私は上記のアイデアの私の実装はいくつかのバグを持っていると考えているが、私は困難な時期にそれを見つけることがあります。

Answer 1

その後編集：私は、私はそれは問題ではなかったので、実行している時間は、まだCのバージョンには高すぎたことに気づい

間違っていました。私はLeetcodeからすべてのテストを受け取り、問題を発見しました。 {3、7、405、436}と量：テストケースのコインについては

各コインのために、私がしようと、ためだけ34486.

これは最も人気のある間、8839私の実装では、18744855本の電話をかけることでしょうできるだけ多くの時間にそれを入れて（while (true)ループ）、それぞれの試行の後に私は再帰呼び出しを行います。それはこのように書きます（コインのために= {1}と量= 3）：

S(3) = min{1 + S(2), 2 + S(1), 3 + S(0)} 

S(2) = min{1 + S(1), 2 + S(0)} 

S(1) = min{1 + S(0)} 

S(0) = 0 

一度だけのコインを試してみて、人気の高いソリューションがないように再帰呼び出しは、残りの部分を処理させるのに十分であるが：

S(3) = min{1 + S(2)} 

S(2) = min{1 + S(1)} 

S(1) = min{1 + S(0)} 

S(0) = 0 

前の答えは：

私はCに同じ厳密解を移植してきた、それが受け入れられてしまったので、私はそれがLeetcodeインフラストラクチャにおけるいくつかの問題であると仮定します。

int coinChange_(int* coins, int coinsSize, int *um, int amount) { 
    if (amount == 0) 
     return 0; 

    if (um[amount] != 0) 
     return um[amount]; 

    int ret = -1; 

    for (int i = 0; i < coinsSize; i++) 
    { 
     int c = coins[i]; 
     int n = 1; 
     while (true) 
     { 
      int a = amount - n * c, m = 0; 
      if (a < 0) 
       break; 
      if (a > 0) 
       m = coinChange_(coins, coinsSize, um, a); 
      if (m != -1) 
      { 
       if (ret == -1) 
        ret = m + n; 
       else 
        ret = m + n < ret ? m + n : ret; 
      } 
      n++; 
     } 
    } 

    um[amount] = ret; 
    return ret; 
} 

int coinChange(int* coins, int coinsSize, int amount) { 
    int *um = calloc(amount + 1, sizeof *um); 
    int ret = coinChange_(coins, coinsSize, um, amount); 
    free(um); 
    return ret; 
}