ডানজিয়ন গেম সমস্যা
একটি M×N গ্রিড দেওয়া আছে। নাইট (০,০)-এ শুরু করে (M-1,N-1)-এ রাজকন্যা বাঁচাতে যাবে। প্রতিটি সেলে স্বাস্থ্য বদলায় (+ve = ওষুধ, -ve = দানব)। নাইট শুধু ডান বা নিচে যেতে পারে। ন্যূনতম প্রাথমিক স্বাস্থ্য কত লাগবে যাতে পথে কখনো স্বাস্থ্য ০ বা নেগেটিভ নয়?
উদাহরণ:
-2(K) -2 3 -5 -10 1 10 30 -5(P)উত্তর: ৬ (পথ: ডান→ডান→নিচ→নিচ)
সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং - রিভার্স)
dp[i][j]= সেল(i,j)-এ পৌঁছালে ন্যূনতম কত স্বাস্থ্য দরকার (সেটা থেকে গিয়ে শেষ করতে)- নিচে ডান কোণ থেকে শুরু করুন (রাজকন্যার সেল)
dp[M-1][N-1] = max(1, 1 - grid[M-1][N-1])- শেষ সারি ও শেষ কলাম পূরণ করুন
- বাকি সেলগুলো:
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - grid[i][j]) dp[0][0]ফেরত দিন
C++ কোড উদাহরণ
{{-2,-2,3},{-5,-10,1},{10,30,-5}}
আউটপুট
6
