akmhmgc · akmhmgc · Sep 27, 2025 · potrue · Sep 29, 2025 · potrue
diff --git a/322/step1.md b/322/step1.md
@@ -0,0 +1,58 @@
+# step1 何も見ずに解く
+
+合計がある金額になるコインの最小枚数は、合計が「ある金額 - コイン」になるコインの最小枚数 + 1が候補になり得る。
+0円からスタートして合計を大きくしていき上の考えを適用すれば良い。
+
+合計金額をN、コインの枚数をMとすると時間計算量はO(MN)
+空間計算量はO(N)
+M,Nはそれぞれ10^4, 12が最大値なので1秒以内に計算が終わる。
+not_existedという変数名が怪しいけど他に思いつかなかった。合計金額を表すことができないという意味にしたい
+
+```ruby
+# @param {Integer[]} coins
+# @param {Integer} amount
+# @return {Integer}
+def coin_change(coins, amount)
+    not_existed = -1
+    fewest_num_coins = Array.new(amount + 1, Float::INFINITY)
+    fewest_num_coins[0] = 0
+    1.upto(amount).each do |sub_amount|
+        coins.each do |coin|
+            next if sub_amount - coin < 0
+            fewest_num_coins[sub_amount] = [fewest_num_coins[sub_amount - coin] + 1, fewest_num_coins[sub_amount]].min
+        end
+    end
+    fewest_num_coins[amount] == Float::INFINITY ? not_existed : fewest_num_coins[amount]
+end
+```
+
+あとは合計に達するまでの最短距離なのでBFSも良さそう。
+
+```ruby
+# @param {Integer[]} coins
+# @param {Integer} amount
+# @return {Integer}
+def coin_change(coins, amount)
+    return 0 if amount.zero?
+
+    not_existed = -1
+    num_coins_and_rest_amount = [[0, amount]]
+    seen_amounts = Set.new
+    seen_amounts << amount
+    while !num_coins_and_rest_amount.empty?
+        next_num_coins_and_rest_amount = []
+        num_coins_and_rest_amount.each do |num_coins, rest_amount|
+            coins.each do |coin|
+                new_rest_amount = rest_amount - coin
+                next if new_rest_amount < 0
+                next if seen_amounts.include?(new_rest_amount)
+                return num_coins + 1 if new_rest_amount == 0
+                seen_amounts << new_rest_amount
+                next_num_coins_and_rest_amount << [num_coins + 1, new_rest_amount]
+            end
+        end
+        num_coins_and_rest_amount = next_num_coins_and_rest_amount
+    end
+    not_existed
+end
+```
diff --git a/322/step2.md b/322/step2.md
@@ -0,0 +1,48 @@
+# step2 他の方の解答を見る
+## DFSの枝刈り
+https://github.com/nittoco/leetcode/pull/38#discussion_r1845464140
+
+```ruby
+# @param {Integer[]} coins
+# @param {Integer} amount
+# @return {Integer}
+def coin_change(coins, amount)
+    return 0 if amount.zero?
+
+    not_existed = -1
+    num_coins_and_sub_amount = [[0, 0]]
+    min_num_coins = Array.new(amount + 1, not_existed)
+    seen_amounts = Array.new(amount + 1, false)
+    while !num_coins_and_sub_amount.empty?
+        num_coins, sub_amount = num_coins_and_sub_amount.pop
+        next if sub_amount > amount
+        next if seen_amounts[sub_amount] && num_coins > min_num_coins[sub_amount]
+        min_num_coins[sub_amount] = num_coins
+        seen_amounts[sub_amount] = true
+        coins.each do |coin|
+            num_coins_and_sub_amount << [num_coins + 1, sub_amount + coin]
+        end
+    end
+    min_num_coins[amount]
+end
+```
+
+```ruby
+        next if seen_amounts[sub_amount] && num_coins > min_num_coins[sub_amount]
+```
+だと、同じ枚数で実現できる合計金額はスキップせずに探索を続けるので、
+例えばcoins = [1, 2]とした時に
+2 1 1
+1 2 1
+1 1 2
+の順番の探索を打ち切らず組み合わせが2^nで増える
+
+```ruby
+        next if seen_amounts[sub_amount] && num_coins >= min_num_coins[sub_amount]
+```
+
+こうすれば　
+2 1 1
+の探索が終わった後に1 2 1の探索は打ち切られるので間に合う。
+
+
diff --git a/322/step3.md b/322/step3.md
@@ -0,0 +1,21 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+結局step1のDPになった。
+
+```ruby
+# @param {Integer[]} coins
+# @param {Integer} amount
+# @return {Integer}
+def coin_change(coins, amount)
+    not_existed = -1
+    fewest_num_coins = Array.new(amount + 1, Float::INFINITY)
+    fewest_num_coins[0] = 0
+    1.upto(amount).each do |sub_amount|
+        coins.each do |coin|
+            next if sub_amount - coin < 0
+            fewest_num_coins[sub_amount] = [fewest_num_coins[sub_amount - coin] + 1, fewest_num_coins[sub_amount]].min
+        end
+    end
+    fewest_num_coins[amount] == Float::INFINITY ? not_existed : fewest_num_coins[amount]
+end
+```
diff --git a/322/step4.md b/322/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正