From 141879e28a00f921a0f8e09d74da6f09cd10c9b0 Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Sat, 27 Sep 2025 20:16:54 +0900
Subject: [PATCH] 322

---
 322/step1.md | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 322/step2.md | 48 +++++++++++++++++++++++++++++++++++++++++++
 322/step3.md | 21 +++++++++++++++++++
 322/step4.md |  1 +
 4 files changed, 128 insertions(+)
 create mode 100644 322/step1.md
 create mode 100644 322/step2.md
 create mode 100644 322/step3.md
 create mode 100644 322/step4.md

diff --git a/322/step1.md b/322/step1.md
new file mode 100644
index 0000000..208caea
--- /dev/null
+++ 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
new file mode 100644
index 0000000..aefa50d
--- /dev/null
+++ 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
new file mode 100644
index 0000000..90dbd12
--- /dev/null
+++ 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
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/322/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正