こんにちは
今回の学びは
・dp表を言葉にできるか？
・エクセルでdp表を書くと頭がスッキリする
問題は。。。
まずは入出力をしっかりおさえましょう。
コインの種類と合計金額が与えられるので
コインを最小に抑えてその合計金額を作り出すには、コイン何枚必要か？
という問題
例えばコインの種類が[1, 2, 5]だったとして、合計金額11を作って欲しいと言われたら、答えは3です。
3まいは、5 + 5 + 1 が正解です
1 + 2 + 2 + 2 + 2 + 2 では6枚となり最小ではありませんね。
総当たり的に考えると
最初のコインを選んで、3通り、次のコインは選ぶのも3通り、そして繰り返し、合計が目的の数を越えたら終了する再帰を考えて意味ます。すると最大再帰はn/ min(N)となるので最悪 nで 毎回n通りの候補があるのでO(n**2)となります
これではパフォーマンス的にダメなので
他のアルゴリズム を考えたいところです
ここでDP的な、段階的に問題を解けないか？と考えます
1, 2, 5と11を段階的に考えるとは
もし[1, 2]しかコインがなかったら！？
もし求める合計が１１ではなく、９だったら？
１１ではなく ７だったらと考えてみます
たて横に適当な、段階的な値をとって。（ここはもっと確かな法則があると思いますが、まだわかっていません）
| 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
[1] | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
[1, 2] | 0, 1, 1, 2, 2, 3, 3,
[1, 2, 5] |
X[i][j]のポイントに来たら
自分のコイン例えば二段目だったら[1, 2]なので
合計６を[1, 2]で作ろうと考えたときに
[1]のみだったら5を作るのに5枚 （5というは6-1から来ている） ーー 条件A
[1]のみだったら4を作るのに4枚 （4というは6-2から来ている） ーー 条件B
必要ということがこれまでのdp表から、わかる。
[1, 2]のみだったら5を作るのに3枚 （5というは6-1から来ている） ーー 条件C
[1, 2]のみだったら4を作るのに2枚 （4というは6-2から来ている） ーー 条件D
これらの4つの条件から、１か２のいづれかを
足せば事足りるので
一番、小さい枚数+1が
合計６を[1, 2] の解答となり
この場合
min(5, 4, 3, 2) + 1 = だから 3 となります
これを
ひたすら続けいます。
timespace analysisは 合計金額 k と コインの枚数 N の表なので
O(k*N) となり spaceも同様に O(k*N)となります
では実装していきましょう
ちょっと気になっているのは先ほどの条件A, B, C, D のA, Cは見なくていいんじゃないか？
という疑問です。なぜなら、それをみるとなると、各行でこれまでのパターンを全部試さないと行けなくなり
条件が2**n乗になってしますからです
だから単純に新しい 数字（その行で追加された新しいコイン）のぶんだけ、つまり常に条件は二つだけ（BとD）ね
そうして初めてO(k*N)だよね
前述のa, b, c, dも見ないといけないと思っていた時の分析はちょっと間違っていて
実際はO(k * (2**N))でとてもべき乗アルゴリズムでダメなことがわかります
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(k * N)です
pseudocode（擬似コード）をかいてみますか。
def solve(S, k):
dp = [ [0] * k for _ in range(len(S)) ]
for i in range(len(dp)):
for j in range(len(dp[0])):
coin = S[i]
this = dp[i-1][j-coin] + 1
that = dp[i][j-coin] + 1
dp[i][j] = min(this or that)
return dp[-1][-1]
実際の実装はこちら
こちらは最初の実装です。細かいケースが、例えば合計k=0だったり、が通りません
こういうのを直すのはすごく時間がかかります。できれば最初から避けたいものです。どうしたら避けられるのでしょうか。やっぱり、めんどくさいけれど、入力をしっかり考えることですね。何気にif文追加した結果こうなった、取りこぼしケースを生んでしまったので、if文追加時に留意する必要があるでしょう。何気にif文を追加せず、エッジケースを意識しながら条件を実装せよ
def coinChange(self, S: List[int], k: int) -> int:
if k <= 0: return 0
dp = [ [0] * k for _ in range(len(S)) ]
for i in range(len(dp)):
for j in range(len(dp[0])):
coin = S[i]
if i == 0:
if (j + 1) % coin == 0:
dp[i][j] = int((j + 1) / coin)
else:
dp[i][j] = -1
else:
try:
this = dp[i-1][j-coin] + 1
except:
this = sys.maxsize
try:
that = dp[i][j-coin] + 1
except:
that = sys.maxsize
dp[i][j] = min(this, that)
# for row in dp:
# print(row)
return -1 if dp[-1][-1] == sys.maxsize else dp[-1][-1]
で、頑張って考えてもなかなか解けませんでした。。。
そういう時は一回コードを捨てることも大事でした。そして今回上手くいったは、いつもはノートにペンでdp表をかいて
考えるんですけど、このdp表を書くという作業と、これを埋めていく作業に関しては実はエクセルの方が適していました。
エクセルで書くとスッキリかけるし、自分としてはとてもやり易かったです。
上の例はcoinが[1, 2, 5]で合計金額11を作る表で、mはmaxsizeをまずは挿入した後、頭上の値と比較して->の値が
最終的なその行列ijの数字です
言葉でやっていることを説明するならば
新しいコインで i行でj-coinすることは、これまでのcoinを含んだ全てのコインを利用して得られる最小枚数。
i-1行で列jは新しいコインを含まずに、得られる最小枚数です
最初の実装の間違いは[i-1][j-coin]としていて、新しいコインを含まないパターンでも、その新しいコインの値段を減らした
場合の最小枚数を参照していたことにありました
やはり、しっかり自分が何をしているのか意識すること
表をしっかりかける事が問題を解くための鍵だと思います。
dp表を言葉にできるか？
がdp問題の肝だと思います
最終的に通ったコードはこちら
class Solution:
def coinChange(self, S: List[int], k: int) -> int:
import logging
logging.basicConfig(level=logging.DEBUG, format="%(message)s")
if k <= 0 or S is None or len(S) == 0: return 0
dp = [ [0] * k for _ in range(len(S)) ]
# for row in dp:
# logging.debug(row)
MAXN = sys.maxsize
#MAXN = 100
for i in range(len(dp)):
for j in range(len(dp[0])):
coin = S[i]
if i == 0:
if (j + 1) % coin == 0:
dp[i][j] = int((j + 1) / coin)
else:
dp[i][j] = MAXN
else:
if i >= 0 and (j - coin) >= 0:
that = dp[i][j-coin] + 1
else:
if coin == j+1: that = 1
else: that = MAXN
dp[i][j] = min(that, dp[i-1][j])
# for row in dp:
# logging.debug(row)
return -1 if dp[i][j] == MAXN else dp[i][j]
実装後です。timespace analysis (時間とスペースの分析）は O(len(S) * k)です
まとめ
今回の学びは
・dp表を言葉にできるか？
・エクセルでdp表を書くと頭がスッキリする
なぜエクセルだとスッキリするのだろうか？今までなぜか避けて気がするのだが。。。
手書きはより記憶に残るので好きだったのだが、このdp表を埋める作業って、何度もやり直ししたするので
すぐノートが表が汚くなる。それならばエクセルとかすぐ消せるし、コピペできて、やり直し作業が速い方が効率が
いいのだろう。つまり繰り返し作業が必要で記憶が重要でない作業は電子媒体の方が適している、という考えに至った。
以上です