DP এবং লোভী উভয়ের সর্বোত্তম সাবস্ট্রাকচার প্রয়োজন। পার্থক্য: লোভী আরও লোভী-পছন্দ সম্পত্তি প্রয়োজন (একটি স্থানীয় সর্বোত্তম বৈশ্বিকভাবে সর্বোত্তম), যখন DP প্রয়োজন যখন আপনাকে একাধিক পছন্দ এবং ওভারল্যাপিং সাবপ্রবলেম বিবেচনা করতে হয়।
Optimal substructure? -- both need this
+ greedy-choice property holds? -> GREEDY (fast, one pass of choices)
+ must compare many sub-solutions / they overlap? -> DYNAMIC PROGRAMMING
# Greedy FAILS for coins {1,3,4}, amount 6 -> 4+1+1 (3 coins)
# DP finds the true optimum: 3+3 (2 coins)
def min_coins(amount, coins):
INF = float('inf')
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1) # try every coin
return dp[amount]
min_coins(6, [1, 3, 4]) # -> 2
লোভী একটি পছন্দে প্রতিশ্রুতিবদ্ধ; DP সব অন্বেষণ করে এবং সেরাটি রাখে।
লোভী সাধারণত O(n log n); DP আরও সময়/স্থান (প্রায়শই O(n·m)) সঠিকতার জন্য বিনিময় করে।
তার সম্পত্তি প্রমাণ না করে লোভী ব্যবহার করা ভুল উত্তর দেয় যা ছোট পরীক্ষা পাস করে। সন্দেহে থাকলে, DP এর দিকে যান বা ব্রুট ফোর্সের বিরুদ্ধে লোভী যাচাই করুন।
যখন এটি বৈধ হয় তখন লোভী বেছে নেওয়া বিশাল সময় সাশ্রয় করে; যখন এটি নয় তখন তৈরি করে নীরব বাগ।
কোন প্যারাডাইম মানানসই জানা এবং এটি প্রমাণ করতে সক্ষম হওয়া একটি সিনিয়র-স্তরের পার্থক্য।
এটি DP দিয়ে অত্যধিক প্রকৌশল এবং একটি অনিরাপদ লোভী পছন্দ দিয়ে অপর্যাপ্ত সরবরাহ উভয়ই প্রতিরোধ করে।