برای دسترسی به سوال 746 لیت‌کد میتونید از این لینک استفاده کنید. سطح این سوال Easy است.

اگر پیشنهادی برای اصلاح پست دارید، می‌تونید از طریق دکمه‌ی "پیشنهاد اصلاح متن" وارد ریپازیتوری وبلاگ در github بشید و تغییرات مورد نظرتون رو پیشنهاد بدید.

فهم مسئله

آرایه‌ای از اعداد نامنفی بهمون داده می‌شه. پلکانی رو در نظر بگیرید که هزینه‌ی رفتن به هر پله، در این آرایه اومده. در ابتدا، در کف هستیم (start) و روی پله‌ها نرفته‌ایم. در هر بار حرکت اجازه داریم یک یا دو پله جلو بریم. هزینه‌ی رفتن به پله i ام، برابر cost[i] است، یعنی مثلا عنصر یکم آرایه، هزینه‌ی رفتن به پله یکم رو نشون می‌ده. بعد از همه‌ی این پله‌ها، پله‌ای هست که قراره اونجا توقف کنیم (end). به دنبال راهی هستیم که هزینه رفتن از start به end، کمترین مقدار ممکن بشه. مثلا برای آرایه [10,15,20] توضیح به این شکل است. روی کف زمین هستیم. چهار پله داریم. هزینه قرارگیری روی پله اول 10، هزینه قرارگیری روی پله دوم 15، هزینه قرارگیری روی پله سوم 20 و هزینه قرارگیری روی پله آخر که مقصد نهایی است، 0 است.

شرایط مسئله

در این مرحله، شرایط خاص مسئله و حالت‌های edge case رو بررسی می‌کنیم. این شرایط باید در توضیحات سوال یا مثال‌ها مشخص شده باشن یا اینکه از پاسخ‌های پیش فرض استفاده کنیم.

• هزینه ایستادن در کف، 0 است.
• هزینه ایستادن در پله‌ی نهایی (مقصد)، 0 است.

راه‌حل منطقی

در این مرحله به دنبال working solution هستیم، یعنی راه حلی منطقی که بتونه مسئله رو حل کنه. به راه حل بهینه فکر نمی‌کنیم. درگیر زبان برنامه نویسی و محدودیت‌های اون هم نخواهیم بود.

این مسئله، یک مسئله‌ی dynamic programming است، اما چطور این موضوع رو بفهمیم؟!

یک مسئله باید دو ویژگی Optimal substructure و overlapping sub-problems رو داشته باشه تا بشه DP رو براش به کار برد.

در بیشتر مواردی که بحث انتخاب جواب بهینه (بیشترین و کمترین) مطرح می‌شه و قراره از بین تعدادی جواب، بهترینش رو انتخاب کنیم، میشه به DP فکر کرد. مثلا در همین سوال، برای رسیدن از کف پله‌ها به بالای اون‌ها، راههای مختلفی با هزینه‌های مختلف وجود دارند. ما به دنبال راهی با کمترین هزینه هستیم. در واقع در brute force‌ترین حالت، باید تمام راه‌های ممکن رو در نظر بگیریم، هزینه‌هاشون رو حساب کنیم و از بین اون‌ها، راهِ با کمترین هزینه رو انتخاب کنیم.

پایه‌ی DP رو میشه در توابع بازگشتی دید. توابع بازگشتی، توابعی هستن که خودشون رو صدا می‌زنن، این صدا زدنِ خود، تا جایی رخ میده که به شرط پایان که در تابع تعریف شده برسیم. کلاسیک‌ترین مثالش، فاکتوریله. مثلا برای محاسبه‌ی 5!، باید 5*4! رو حساب کنیم. برای محاسبه‌ی 4!، باید 4*3! رو حساب کنیم. برای محاسبه‌ی 3!، باید 3*2! رو حساب کنیم. برای محاسبه‌ی 2!، باید 2*1! رو حساب کنیم. مقدار 1! رو می‌دونیم که برابر 1 میشه و این شرطِ پایان الگوریتمه. حالا همین مسیر رو برمی‌گردیم. مقدار 2! برابر میشه با 2. مقدار 3! برابر میشه با 6. مقدار 4! برابر میشه با 24. مقدار 5! برابر میشه با 120.

ارتباط DP و بازگشتی

اما ارتباط توابع بازگشتی با DP چیه؟ مسئله‌ی Min Cost Climbing Stairs که بالا بیان شد رو چطور میشه به DP و بازگشتی ربط داد؟ با توجه به صورت مسئله، برای رسیدن به پله نهایی، میشه از پله قبل یا قبل‌ترش استفاده کرد، چون سوال گفته که “در هر بار حرکت اجازه داریم یک یا دو پله جلو بریم”.

فرض کنیم مثالی به صورت [20,25,30,5] داریم. پله‌ی صفرم رو پله‌ی با هزینه 20، پله‌ی یکم رو پله‌ی با هزینه 15، پله‌ی دوم رو پله‌ی با هزینه 30، پله‌ی سوم رو پله‌ی با هزینه 5 و پله‌ی چهارم رو که قراره روی اون بایستیم و هزینه‌اش 0 است، پله‌ی آخر در نظر می‌گیریم. رسیدن به پله‌ی 4 چطور ممکنه؟ اینکه در پله‌ی 3 یا 2 باشیم. هزینه‌ی رسیدن به پله‌ی 4 چطور مینیمم میشه؟ فرض کنید برای رسیدن از start به پله‌ی 3 هزینه‌ی x رو پرداخته‌ایم و برای رسیدن از start به پله‌ی 2 هزینه‌ی y رو پرداخته‌ایم.حالا برای رفتن از هر یک از این دو پله به پله‌ی 4 هم هزینه‌ای باید بپردازیم که 0 هست. پس هر از اون پله‌ای که تاکنون هزینه کمتری به ما تحمیل کرده (مینیمم بوده) به پله‌ی 4 میریم.

همین موضوعی که در مورد پله‌ی 4 بیان شد، در مورد پله‌ی 2 و 3 هم وجود داره.

رسیدن به پله‌ی 2 چطور ممکنه؟ اینکه از پله‌ی 0 یا 1 به اون بیایم. هزینه‌ی رسیدن به پله‌ی 2 چطور مینیمم میشه؟ به این صورت که مجموعِ هزینه‌های قبلی که ما رو به پله‌ی 0 یا 1 رسونده، به اضافه‌ی هزینه‌ای که قراره ما رو از 0 یا 1 به 2 ببره، مینیمم بشه.

رسیدن به پله‌ی 3 چطور ممکنه؟ اینکه از پله‌ی 2 یا 1 به اون بیایم. هزینه‌ی رسیدن به پله‌ی 3 چطور مینیمم میشه؟ به این صورت که مجموعِ هزینه‌های قبلی که ما رو به پله‌ی 2 یا 1 رسونده، به اضافه‌ی هزینه‌ای که قراره ما رو از 2 یا 1 به 3 ببره، مینیمم بشه.

همین موضوع برای موارد دیگر هم برقراره. ما از انتها شروع کردیم و به ابتدا رسیدیم. یعنی حساب کردیم برای رسیدن به پله‌ی 4 چطور هزینه رو مینیمم کنیم و همین طور اومدیم پایین‌تر تا جایی که دیگه پله‌ای وجود نداشت. هر بار مسئله‌ای مشابه ولی کوچکتر ایجاد شد. در واقع تابع (فرمول) همونه اما هر بار ورودی‌ها فرق می‌کنن. به این رویکرد، Top-Down میگن.

این پایین اومدن تا کجا ادامه داره؟ در مسئله‌ی فاکتوریل، تا 1 اومدیم عقب، چون 1! رو می‌دونیم و نیاز نیست براش محاسبه انجام بدیم، پس اون رو به عنوان شرط پایان تعریف کردیم. در مسئله‌ی Min Cost Climbing Stairs، تا زمانی که به هزینه‌ی پله 0 یا 1 برسیم، باید بیایم عقب، چون در حرکت اول، میشه روی یکی از این پله‌ها ایستاد. از طرفی، وقتی روی پله‌‌ی 0 یا 1 هستیم، مینیمم هزینه‌ای که تا اونجا پرداخته‌ایم، همون هزینه‌ای است که برای ایستادن رو اونها داده‌ایم و قبلش هزینه‌ای پرداخت نشده. هزینه‌ی ایستادن روی کف (که مثلا میشه اون رو به عنوان پله‌ای با شماره‌ی منفی در نظر گرفت) 0 است.

عبارت بالا رو چطور فرموله کنیم؟ به این صورت:

1
2
3

min cost (i) = cost(i) + MIN(min cost (i-1), min cost (i-2))
min cost (0) = cost(0)
min cost (1) = cost(1)

تا اینجا، تونستیم مسئله رو به حالت بازگشتی بیان کنیم. مشابه با مسئله‌ی فاکتوریل، همون فرمول اما هر بار با ورودی‌های کوچکتر بیان میشه تا جایی که به شرطِ پایان برسه، اما هنوز از پتانسیل‌های DP استفاده نکرده‌ایم.

در حالت ابتدایی، کد به صورت زیر خواهد بود.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public int MinCostClimbingStairs(int[] cost)
{
  int n = cost.Length;
  return Math.Min(MinCost(n - 1, cost), MinCost(n - 2, cost));
}

public int MinCost(int i, int[] cost)
{
  if (i < 0) return 0;
  if (i == 0 || i == 1) return cost[i];
  return cost[i] + Math.Min(MinCost(i - 1, cost), MinCost(i - 2, cost));
}

پیچیدگی زمانی این الگوریتم O(2n) است، چون تابع MinCostClimbingStairs از رویکرد بازگشتی استفاده می‌کند و در هر فراخوانیِ بازگشتیِ تابع MinCost، دو فراخوانیِ بازگشتیِ دیگر با ورودیهای i - 1 و i - 2 انجام می‌دهد. این نوع فراخوانی، یک ساختارِ شبیه binary-tree ایجاد می‌کند که هر node‌ای، دو بچهnode دارد. بنابراین تعداد فراخوانی‌ها به شکل نمایی و با اندازه‌ی آرایه cost زیاد می‌شود. فراخوانی‌ها تا زمانی که به (i < 0, i == 0, i == 1) برسیم ادامه دارد.

پیچیدگی حافظه‌ای، O(n) است، چون تابع به صورت بازگشتی پیاده‌سازی شده و هر فراخوانی بازگشتی، یک frame به call stack اضافه می‌کند، حداکثر عمق call stack برابر با اندازه‌ی آرایه cost است.

روش top-down

حالا قصد داریم از DP استفاده کنیم تا الگوریتم رو بهبود بدیم. درختی که طبق آن محاسبات انجام می‌شود را رسم می‌کنیم. در نمودار زیر، c نشان‌دهنده cost و mC نشان‌دهنده minimum Cost است.

نکته واضح در درخت بالا، تکراری بودن یک سری از محاسبات است، مثلا mC(i-3) بارها در جاهای مختلف محاسبه شده. بهتر نیست که این مقادیر تکراری رو، وقتی اولین بار محاسبه میشن در جایی ذخیره کنیم و در موارد بعدی که بهشون نیاز شد، از همون مقدار ذخیره شده استفاده کنیم و دوباره محاسبات انجام ندیم؟ قطعا بهتره. به کار memoization گفته می‌شه. وقتی به یک گره در درخت بالا می‌رسیم، اگه مقدارش رو از قبل در جایی ذخیره کرده باشیم، دیگه نیاز نیست اون گره رو تا پایین (رسیدن به شرط پایان) ادامه بدیم.

این ویژگی رو چطور وارد کد کنیم؟

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int MinCostClimbingStairs(int[] cost) {
  int n = cost.Length;
  if (n == 0) return 0;
  if (n == 1) return cost[0];

  int[] dp = new int[n];

  for (int i = 0; i < n; i++) {
    if (i < 2) {
      dp[i] = cost[i];
    }
    else {
      dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);
    }
  }

  return Math.Min(dp[n - 1], dp[n - 2]);
}

در این حالت پیچیدگی زمانی O(n) است، چون یک پیمایش روی آرایه ورودی انجام می‌دهد. پیچیدگی حافظه‌ای هم O(n) است، چون یک آرایه کمکی با طول n به کار گرفته شده است. به این صورت با رویکرد dynamic programming توانستیم الگوریتم را بهینه‌تر کنیم.

روش bottom-up

مسئله حل شده است، اما برای یادگیری بیشتر می‌توان از دیدِ دیگری هم به آن نگاه کرد. در روش قبلی از دید top-down به مسئله پرداختیم، در روش top-down، از انتها به ابتدا اومدیم، هر بار یک frame روی call stack اضافه کردیم تا به ابتدا (شرط پایان) رسیدیم و دوباره برگشتیم و به انتها رسیدیم. در واقع از رویکرد بازگشتی استفاده کردیم. در این روش، مسئله‌ی بزرگ، به زیر مسئله‌های کوچک تبدیل می‌شه و با بازگشت روی اونها، به جوابِ مسئله‌ی بزرگ می‌رسیم.

رویکرد دیگری هم به نام bottom-up وجود داره که از پایین شروع می‌کنه و به بالا می‌رسه. ایده‌ی اصلیِ bottom-up اینه که مسئله رو از recursive به iterative تبدیل کنه. مسئله‌ی فیبوناچی رو در نظر بگیرید. برای محاسبه‌ی عدد nام، در رویکرد top-down، از n به n-1، از n-1 به n-2 و همینطور ادامه می‌دیم تا از 3 به 2 و از 2 به 1 برسیم. با دانستن جملات 1 و 2، همین مسیر رو برمی‌گردیم تا به n برسیم. دو واقع مسئله رو شکستیم و با محاسبه و ذخیره‌ی پاسخ زیرمسئله‌ها، به جواب نهایی رسیدیم. در رویکرد bottom-up، از 1 به 2، از 2 به 3 و همینطور ادامه می‌دیم تا از n-1 به n برسیم. این روش بهینه‌تره، اما علت این که همیشه از رویکرد bottom-up استفاده نمی‌کنیم اینه که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله‌ی اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public static int MinCostClimbingStairs(int[] cost) {
  int n = cost.Length;
  if (n == 0) return 0;
  if (n == 1) return cost[0];

  int dpOne = cost[0];
  int dpTwo = cost[1];

  for (int i = 2; i < n; i++) {
    int current = cost[i] + Math.Min(dpOne, dpTwo);
    dpOne = dpTwo;
    dpTwo = current;
  }
  
  return Math.Min(dpOne, dpTwo);
}

پیچیدگی زمانی O(n) و پیچیدگی حافظه‌ای O(1) است.

منابع

udemy