سوال ۱۱

در خانه‌ی پایین-چپ جدول زیر، یک لاک‌پشت قرار دارد و می‌خواهد به خانه‌ی بالا-راست برسد. روی هر خانه، ارتفاع آن نوشته شده است. لاک‌پشت در هر مرحله می‌تواند یک واحد به راست یا بالا برود و در هر گام، به اندازه‌ی اختلاف ارتفاع دو خانه خسته می‌شود (حتی اگر ارتفاع کم شود). کمینه‌ی مجموع میزان خستگی در مسیر چیست؟

  1. 2000
  2. 3200
  3. 3800
  4. 1920
  5. 2310

پاسخ

گزینه‌ی ۴ درست است.

اگر $b[i][j]$ برابر ارتفاع خانه‌ی واقع در سطر $i$ و ستون $j$ و هم‌چنین $a[i][j]$ برابر کم‌ترین میزان خستگی لاک‌پشت برای رسیدن از مبدأ به این خانه باشد، داریم: $$a[i][j] = min\Big(\big|b[i][j] - b[i - 1][j]\big| + a[i - 1][j], \big|b[i][j]-b[i][j-1]\big| + a[i][j - 1] \Big)$$ این رابطه با بررسی دو حالت ورود به خانه‌ی مذکور گفته شده است (از چپ یا پایین). حال با به دست آوردن مقادیر $a[i][j]$ به صورت پویا، مقادیر زیر به دست می‌آید:

پس پاسخ برابر ۱۹۲۰ است.