最低金券問題のJavaScript解法

前言
最近牛客ネットで問題を書いて、金券の問題に出会いました.午後の時間をかけて研究しました.(アルゴリズムとデータ構造を復習し始めたばかりです.)この文章を書いて記録してみます.
テーマ転送ゲート:https://www.nowcoder.com/question/next?pid=21910781&qid=894518&tid=31674041 問題6
 
問題
最近あるデパートでは記念日のため、「0元買い」のイベントが始まりました.イベントでは、消費者が持っているクーポンを組み合わせることで、指定商品を0元で買うことができます.
賢い団体は計算方法を使って彼の速い計算を助けたいです.指定された価格の商品に対して、金券を使ってその価格を割り出せばいいですが、使用した金券の総額面は商品の価格を超えてはいけません.金券の数が限られているので、少ない金券の枚数を使うと価値が最大化されます.
100元の商品があると仮定して、金券は50元、30元、20元、5元の4種類があります.最高の特典は50元のクーポン2枚です.65元の商品があれば、30元のクーポン2枚と5元のクーポン1枚がベストです.
金券の計算を実現するためにコードを使ってください.
 
思考
愚かな私の最初の反応は貪欲なアルゴリズムを使っていました.しかし、率が高くないことを発見して、貪欲なアルゴリズムを思い出しました.(貪欲アルゴリズムは何ですか?他の文章を探しに行きましょう.)動的な計画を使います.たくさんの解法がありますが、他の言語を使っています.特に大きい人はjsで書いていますが、注釈の説明がなくて、私の顔がぼんやりしています.
それから他の言語で流れを分かりました.JSと結合してコードを完成しました.
 
コード

var target_money = 3;
var price_list = [2, 5, 7, 20, 50];
console.log(fn(target_money, price_list));

function fn(tg, pl) {
    var dp = [];
    //      ，      0    0 
    //      
    for (let i = 0; i < pl.length; i++) {
        dp.push([0])
    }
    //      
    for (let i = 1; i <= tg; i++) {
        if (i % pl[0] == 0) dp[0][i] = parseInt(i / pl[0]);
        // pl[0]    ，       
        else dp[0][i] = Infinity;
    }
    //        
    for (let i = 1; i <= tg; i++) {
        for (let j = 1; j < pl.length; j++) {
            //    pl[j]   
            if (i < pl[j]) dp[j][i] = dp[j - 1][i];
            //          
            else if (i == pl[j]) dp[j][i] = 1;
            else {
                //    
                var left = dp[j - 1][i];
                //    
                var up = dp[j][i - pl[j]] + 1;
                //       
                dp[j][i] = left < up ? left : up;
            }
        }
    }
    var res = dp[pl.length - 1][tg]
    // console.log(dp)
    return res == Infinity ? "Impossible" : res;
}

 
説明
ダイナミック企画は、表を作成します.dpは二次元配列で、横にクーポンの種類を表します.縦には構成される金額が必要です.前j種の金券を使ってi元を構成するために必要な金券の数をdp(j,i)で表します.横のクーポンの金額は小さい順に並べて、縦は0から目標までの金額です.
dp(j,i)の値はdp(j-1,i)とdp(j,i-pl[j]+1の中小の一つに等しく、前の代表は金額種類jの金券を使わずに金額iを解決するもので、後の代表金額iは現在の金券金額を差し引いた後、現在の金額の金券券で解決する最少枚数となります.今のクーポンの金額を減らしましたので、今のクーポンを使ったのと同じです.後はもう一枚追加します.
初期化:前j種の代価券で0元を解決した場合、結果は全部0枚です.0番目の金券で0からtgの金額を処理するのは二つの場合だけです.割り切れるなら、枚数を記入します.割り切れないなら、テーマの要求でjsの無限大Infinityにします.dp表の一番左と一番上に値があります.後ろの数は全部左と上の数を比較します.
 
終了
先が見えたら、アルゴリズムをマスターして、頑張ってください.