در خانهی پایین-چپ جدول زیر، یک لاکپشت قرار دارد و میخواهد به خانهی بالا-راست برسد. روی هر خانه، ارتفاع آن نوشته شده است. لاکپشت در هر مرحله میتواند یک واحد به راست یا بالا برود و در هر گام، به اندازهی اختلاف ارتفاع دو خانه خسته میشود (حتی اگر ارتفاع کم شود). کمینهی مجموع میزان خستگی در مسیر چیست؟
پاسخ
گزینهی ۴ درست است.
اگر $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]$ به صورت پویا، مقادیر زیر به دست میآید:
پس پاسخ برابر ۱۹۲۰ است.