ENDEAR
ابدأ مجاناً
خوارزميةاحترافي

البرمجة الديناميكية: صرف العملات

أوجد أقل عدد من القطع النقدية يكوّن مبلغاً، في مسألة يفشل فيها اختيار القطعة الأكبر أولاً.

الزمن
O(n·m)
الذاكرة
O(n)

تتبّعها خطوة بخطوة

الخطوة 1 من 15
1function coinChange(coins, amount) {2  const dp = new Array(amount + 1).fill(Infinity);3  dp[0] = 0;4  for (let a = 1; a <= amount; a++) {5    for (const c of coins) {6      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;7    }8  }9  return dp[amount] === Infinity ? -1 : dp[amount];10}
coins
= [1, 3, 4]
  1. 00
  2. ∞1
  3. ∞2
  4. ∞3
  5. ∞4
  6. ∞5
  7. ∞6

dp[0] = 0: صفر من القطع يكوّن 0. كل مبلغ آخر يبدأ بـ ∞، أي لا يمكن الوصول إليه بعد.

درس احترافي

افتح الشرح الكامل

هذا الدرس جزء من الخطة الاحترافية، التي تفتح كل خطوة في كل درس، إضافة إلى تدريبات الأنماط وتقارير الإتقان.

اطّلع على الأسعار

كيف تعمل

مع القطع 1 و3 و4، يختار الأسلوب الجشع 4 + 1 + 1 للمبلغ 6، بينما 3 + 3 تحتاج قطعتين فقط. البرمجة الديناميكية تجرّب كل خيار دون تكرار العمل: dp[a] هو أقل عدد من القطع للمبلغ a، ولكل قطعة c تكون dp[a − c] + 1 قيمة مرشّحة. املأ dp من 0 حتى المبلغ. الزمن O(n·m) لمبلغ n و m من القطع، والذاكرة O(n).

تدرّب على اكتشاف هذا النمط →