前言

昨日の面接の时に突然动态计画に言及して、结局面接官は私に动态计画は何ですかと闻いて、私は意外にも一时的に表现することができなくて、ここで自分の话で缲り返し练习してみます:动态计画は先に大きい问题の子の问题を探し当てて、子の问题の解を中间の结果として最终の问题を解いて、しかも子の问题の解は局部が最も良いです.

動的計画問題の一般的な解題手順

状態を決定する:一般的に状態

を配列で表すことができる.

化成サブ問題:問題の最後のステップがどのように解くか(例えばステップジャンプ問題の最後は一般的にステップアップとステップアップ2を調整してdp[n]=dp[n-1]+dp[n-2]

を得ることができる

初期条件と境界状況に注意(dp[0]=1を設定)

計算順序は下から上(再帰的には上から下への順序が一般的)

.

小銭両替

タイトルの説明

異なる額面のコインcoinsと総金額amountを与えます.合計金額にまとめるのに必要な最小限のコイン数を計算する関数を作成します.合計金額を構成できるコインの組み合わせがない場合は、-1を返します.
コインの数は無限だと思います.
例1:
入力:coins=[1,2,5],amount=11出力:3解釈:11=5+5+1
考え方:

は、まず、dp[amount+1]配列で表す使用する最小の硬貨数

を決定する.

最後のステップはいずれにしてもコインcoinを1つ追加して金額がちょうどamountになるようにし、その後、これを追加するコインと追加しないコインの数を比較すると少ないので、繰返し式min(dp[amount-coin]+1,dp[amount])

は結果dp[amount]

を返す

jsコード

var coinChange = function (coins, amount) {
     
//               
  let dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  console.log(dp);
  let len = coins.length;

  for (let i = 0; i <= amount; i++) {
     
    for (let j = 0; j < len; j++) {
     
    //   ：                             
    //                                
      if (i >= coins[j] && dp[i - coins[j]] !== Infinity) {
     
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
      }
    }
  }
  if (dp[amount] === Infinity) {
     
    return -1;
  }
  return dp[amount];
};


console.log(coinChange([1, 2, 5], 11));

小銭両替II

タイトルの説明

異なる額面のコインと総額を指定します.関数を書き出して総額にまとめることができるコインの組み合わせ数を計算します.各額面のコインに無限があると仮定します.
例1:
入力:amount=5,coins=[1,2,5]出力:4解釈:合計金額にまとめるには4つの方法がある:5=5=2+2+15=2+1+15=1+1+1+1+1+1

構想

実はこの問題と階段の調整は実は同じタイプの問題です.
完全なリュックサックの組み合わせの問題--容量amountを満たすリュックサックは、いくつかのコインの組み合わせがあります

dp[j]は、jの容量を満たすリュックサックを表すいくつかの硬貨の組み合わせ転移方程式を表す:dp[j]=dp[j]+dp[j-coin]

現在j容量を満たす方法数=前にj容量を満たす硬貨の組み合わせ数+j-coin容量を満たす硬貨の組み合わせ数すなわち現在の硬貨coinの添加は、j-coin容量の組み合わせ数を加えることができ、01リュックサックと差が少ないが、唯一の違いは硬貨が繰り返し使用できることであり、1つの逆順の違いはdp[-1]、すなわちdp[amount]

を返すことである.
他の人の考えを見て、最初はこのように書いたコードです.

var change = function (amount, coins) {
     
  //  dp[i]         i         
  let dp = new Array(amount + 1).fill(0);
  dp[0] = 1

  for (let i = 1; i <= amount; i++) {
     
    for (let j = 0; j < coins.length; j++) {
     

      dp[i] = dp[i - coins[j]] + dp[i]
    }
  }

  return dp[amount];

};


console.log(change(5, [1, 2, 5]))

そしてずっと間違っていて、結果は真実の答えより大きくて、それから私はdebugerの後でこれが求めた配列数の結果であることを知っていて、答えは組み合わせ数を求めて、そして私はleetcodeで次の文をひっくり返しました
組み合わせ数を求めると外層forが物を巡り、内層forがリュックサックを巡る.配列数を求めると外層forがリュックサックを巡り、内層forが物を巡ります.
だから遍歴の順番を変えて

var change = function (amount, coins) {
     
  //  dp[i]         i         
  let dp = new Array(amount + 1).fill(0);
  dp[0] = 1

  for (let i = 0; i < coins.length; i++) {
     
    for (let j = coins[i]; j <= amount; j++) {
     
      dp[j] = dp[j] + dp[j - coins[i]]
    }
  }

  return dp[amount];

};


console.log(change(5, [1, 2, 5]))