در خانهی پایین-چپ جدول زیر، یک لاکپشت قرار دارد و میخواهد به خانهی بالا-راست برسد. روی هر خانه، ارتفاع آن نوشته شده است. لاکپشت در هر مرحله میتواند یک واحد به راست یا بالا برود و در هر گام، به اندازهی اختلاف ارتفاع دو خانه خسته میشود (حتی اگر ارتفاع کم شود). کمینهی مجموع میزان خستگی در مسیر چیست؟
پاسخ
گزینهی ۴ درست است.
اگر b[i][j] برابر ارتفاع خانهی واقع در سطر i و ستون j و همچنین a[i][j] برابر کمترین میزان خستگی لاکپشت برای رسیدن از مبدأ به این خانه باشد، داریم: a[i][j]=min(|b[i][j]−b[i−1][j]|+a[i−1][j],|b[i][j]−b[i][j−1]|+a[i][j−1]) این رابطه با بررسی دو حالت ورود به خانهی مذکور گفته شده است (از چپ یا پایین). حال با به دست آوردن مقادیر a[i][j] به صورت پویا، مقادیر زیر به دست میآید:
پس پاسخ برابر ۱۹۲۰ است.