ضریب دو جمله ای | DP-9
با توجه به مقادیر n و k عدد صحیح ، وظیفه یافتن مقدار ضریب دوجمله ای C(n, k) است.
یک ضریب دو جمله ای C(n, k) را می توان به عنوان ضریب x^k در بسط (1 + x)^n تعریف کرد.
یک ضریب دوجمله ای C(n, k) همچنین تعداد راه هایی را نشان می دهد، بدون توجه به ترتیب، که k شیء را می توان از بین n شیء به طور رسمی تر انتخاب کرد، تعداد زیر مجموعه های k-عنصر (یا k-ترکیب) یک n-عنصر. مجموعه
استفاده از بازگشت - O(2 ^ n) زمان و O(n) فضا
ایده استفاده از بازگشت برای یافتن C(n، k) است. مقدار C(n, k) را می توان به صورت بازگشتی با استفاده از فرمول استاندارد زیر برای ضرایب دو جمله ای محاسبه کرد . C(n، k) = C(n-1، k-1) + C(n-1، k) . C(n, 0) = C(n, n) = 1. بنابراین ما فقط باید C(n-1, k-1) و C(n – 1, k) را فراخوانی بازگشتی انجام دهیم . شرایط پایه زمانی خواهد بود که k = 0 یا مقدار k و n برابر باشد.
DP از بالا به پایین (حافظه نویسی ) – O(n * k) زمان و O(n * k) فضا
لازم به ذکر است که تابع فوق مشکلات فرعی مشابه را بارها و بارها محاسبه می کند. و دارای دو ویژگی برنامه نویسی پویا :
1. زیرساخت بهینه :
مقدار C(n، k) بستگی به راه حل های بهینه زیرمسئله های C(n-1، k-1) و C(n-1، k) دارد . با افزودن این زیرسازه‌های بهینه، می‌توانیم مقدار کل C(n, k) را به طور موثر محاسبه کنیم.
2. مشکلات فرعی همپوشانی :
هنگام اعمال یک رویکرد بازگشتی در این مسئله، متوجه می‌شویم که مشکلات فرعی خاصی چندین بار محاسبه می‌شوند. درخت بازگشتی برای n = 5 و k = 2. تابع C(3, 1) دو بار فراخوانی می شود. برای مقادیر بزرگ n، مشکلات فرعی مشترک زیادی وجود خواهد داشت.
راه حل بازگشتی برای محاسبه ضریب دوجمله ای C(n,k) شامل دو پارامتر است: n که تعداد کل عناصر را نشان می دهد و k که تعداد عناصر مورد نظر را نشان می دهد. برای محاسبه موثر این مقدار بدون محاسبات اضافی، از برنامه‌نویسی پویا با حافظه‌گذاری استفاده می‌کنیم. ما یک آرایه دوبعدی (جدول) با اندازه (n+1)×(k+1 ) داریم که در آن n می تواند از 0 تا n و k از 0 تا k باشد. جدول یادداشت نتایج زیرمشکلات قبلا محاسبه شده را ذخیره می کند. اگر مقدار یک جفت خاص (n,k) قبلا محاسبه شده باشد، به سادگی آن را برمی گردانیم. اگر نه، آن را به صورت بازگشتی محاسبه می کنیم
استفاده از DP از پایین به بالا (جدول بندی) - O(n * k) زمان و O(n * k) فضا
رویکرد مشابه روش قبلی است . فقط به جای شکستن مسئله به صورت بازگشتی ، ما به طور مکرر راه حل را با محاسبه از پایین به بالا ایجاد می کنیم . یک جدول dp[][] طوری نگهداری کنید که dp[i][j] تعداد تمام مسیرهای ممکن منحصر به فرد را برای رسیدن به سلول (i, j) ذخیره کند .
مورد پایه:
برای i = j و 0 <= i <= n، dp[i][j] = 1
برای j = 0 و 0 <= j <= min(i, k) , dp[i][j] = 1
مورد بازگشتی:
برای i > 1 و j > 1، dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
استفاده از Space Optimized DP – O(n * k) Time و O(k) Space
در رویکرد قبلی با استفاده از برنامه نویسی پویا ، ما یک رابطه بین حالت ها را به صورت زیر استخراج کردیم:
dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
برای این کار نیازی به حفظ کل ماتریس نداریم. ما فقط می توانیم یک آرایه به طول k را حفظ کنیم و هر بار dp[j-1] را به dp[j] اضافه کنیم.
از یک آرایه 1 بعدی dp[] با اندازه k+1 برای ذخیره ضرایب دوجمله ای استفاده کنید و پیچیدگی فضا را به O(k) کاهش دهید .
dp[0] = 1 را تنظیم کنید که نشان دهنده nC0=1 است.
dp[j] را به ترتیب معکوس با استفاده از مقادیر قبلی از همان آرایه به روز کنید .
هر ورودی dp[j] به صورت dp[j] + dp[j-1] برای هر ردیف به‌روزرسانی می‌شود .
مقدار نهایی dp(n,k) در dp[k] ذخیره شده و برگردانده می شود.
