Dungeon Game

Saksham Gupta
Last Updated: May 13, 2022

Introduction

Dynamic programming is an all-time favorite topic when it comes to tech interviews, and solving its classical problems surely helps you to clear the basics. But the problem, the dungeon game is not like any other DP problem, it sure looks familiar, but it isn’t. Now without wasting any more time, let’s jump to the problem.

Understanding the Problem

We have been given a dungeon (M x N grid). Every cell in the grid contains a number. The number may be positive or negative. We can move across a cell only if we have positive points (>0). Whenever we pass through a cell, points in that cell are added to our overall points.

We need to find the minimum initial energy(also referred to as health) required to reach cell (M - 1, N - 1) where our princess is waiting from (0, 0) by following these certain set of rules:

  • From a cell (i, j) we can move to (i + 1, j) or (i, j + 1).
  • We cannot move from (i, j) if your overall points at (i, j) are <= 0.
  • We have to reach at (M - 1, N - 1) with minimum positive points, i.e., > 0.

Let's understand this better by the following example.

Let say the following dungeon is given to us,

-1

-3

1

-3

-4

4

10

20

-2

 

Now 5 would be the minimum initial points needed to reach the end. The path taken is as follows. (This is just one of the possibilities)

(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2).

Explanation

As per our chosen path, at position (0,0), the health will be decreased by -1. Then we will go down, so now this -3 will add up to -1. After that, we can see all are positive healths, so we will not lose any more health. Thus in total, we need health = -(-1 - 3) + 1 = 5.

This might be a bit odd for you to grasp but believe me, you’ll get the idea as we will proceed further.

Let’s first look at the brute force approach and then, we will optimize it further.

Brute Force

The best idea is to devise the recurrence relation. The recurrence relation is quite intuitive, as we have only two options to choose from: either go down or right. So, at any point of a particular cell, if we know the answer for min health requirement if we go right vs we go down, then we can easily choose between them.

We will create a helper function getVal(MAT, i, j), which will take three arguments, ‘MAT’ (dungeon) and two variables, ‘i’ and ‘j’. The variables ‘i’ and ‘j’ will represent the row and column index and will help us to iterate over the dungeon. Let’s look at the working of the function

  1. Base Case:

       1. If we go out of bounds, i.e., i == ’N’ or j == ’M’, simply return INF.

       2. If we reach the princess, i.e., i == ’N - 1’ and j == ’M - 1’, we will check if the value of ‘MAT[i][j]’ is positive or negative. If it is positive, we will return 1 (given            in the problem statement as we need a minimum of 1 energy to cross the cell), and if it is negative, we will return -MAT[i][j] + 1 because this is the energy              that will get exhausted.

2. Recursive calls:

  1. As we are allowed to go only right or down, thus we will make two calls to this recursive function and store their answers in two variables ‘RIGHT_COST’ and ‘DOWN_COST’.
  2. Now the ‘MINIMUM_HEALTH’ required would be the minimum of the two above values minus the value of matrix at that point, i.e., min( RIGHT_COST, DOWN_COST) - MAT[i][j].

But this is not our final answer. As done with the base case earlier, we will check if ‘MINIMUM_HEALTH’ is positive or negative. If it’s positive, we will return 1 as this is the minimum amount of energy required to cross a cell. Otherwise, we have to return 

-MINIMUMHEALTH + 1.

Below is the code for the above implementation.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getVal(vector<vector<int>> &mat, int i = 0, int j = 0)
{
    int n = mat.size();
    int m = mat[0].size();

    // Base case. When we go out of bound of dungeon.
    if (i == n || j == m)
        return 1e9 + 5;

    // When we have reached our destination.
    if (i == n - 1 and j == m - 1)
        return (mat[i][j] <= 0) ? -mat[i][j] + 1 : 1;

    // Making recursive calls for both the options.
    int rightCost = getVal(mat, i, j + 1);
    int downCost = getVal(mat, i + 1, j);

    // Finding min health required using above values.
    int minHealthRequired = min(rightCost, downCost) -mat[i][j];

    /// Return final answer.
    return (minHealthRequired <= 0) ? 1 : minHealthRequired;
}

int calculateMinimumHP(vector<vector<int>> &dungeon)
{
    return getVal(dungeon);
}

int main()
{
    // Taking Input.
    int m, n;
    cout << "Enter number of rows: ";
    cin >> m;
    cout << "Enter number of columns: ";
    cin >> n;
    cout << "Enter elements of dungeon: " << endl;
    vector<vector<int>> dungeon(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> dungeon[i][j];
        }
    }

    cout << "Minimum energy required in the beginning is: " << calculateMinimumHP(dungeon);
    return 0;
}

Input

Enter number of rows: 3
Enter number of columns: 3
Enter elements of dungeon: 
-1 -3 3
-3 -4 4
10 20 -2

Output

Minimum energy required in the beginning is: 5

Time Complexity

O(2 ^ (M + N))where ‘M’ is the number of rows of the dungeon matrix, and ‘N’ is the number of columns.

As every time we are making two calls to the recursive function.

Space Complexity

O(M + N), where ‘M’ is the number of rows of the dungeon matrix, and ‘N’ is the number of columns.

This is the height of the recursion tree and hence the space used by the recursion stack.

Now we don’t want exponential time complexity, and if we look very closely, we can see there are overlapping subproblems. When we hear overlapping subproblems, the first thing that comes to mind is dynamic programming. But this problem is a bit different than usual dynamic programming problems, so let’s first look at the thought process for the same.

DP Thought Process

When you’re in some room in the dungeon, you need enough health to do two things.

  • Survive the health cost of the room, and
  • Have enough health left over to move to a different room, either right or down.

If we add these two together, the sum represents the amount of health we need to exist at a particular location. Luckily, we already know one of these: the amount of health we need to survive the health cost of the room. 

What about the second one? 

The amount of health we need to move to a different room is simply the amount of health we need to exist in another room, which is the exact kind of thing we’re calculating! This means that we can work backward from the end, where the princess(DUNGEON[M - 1][N - 1]) is, up to the start to get our answers.

Remember that since we want to minimize the health we need at the start, of the two actions we can take, going right or down, we will take the one that requires the less amount of health.

But what about the end?

You can’t move to a different room once you hit the end!

Yes, this is correct! That’s why we’ll have to do something special for the end, and pretend that the cost we need to move to a different room is 1. This works perfectly fine because it is the exact same thing as saying that once we hit the end and pay the associated health cost, we must have at least 1 health left over to be alive! This is the end criteria we need to meet, which we know from the problem statement itself.

Approach and Algorithm

To begin, we should keep a 2D array ‘DP’ of the same size as the grid, where DP[i][j] indicates the minimum points that ensure the travel to the destination will continue before entering the cell (i, j). Now DP[0][0] is our ultimate solution which is quite obvious. As a result, we must fill the table from the bottom right corner to the left top in order to solve this problem.

But how will we fill the table?

Before filling the table, let us first determine the minimum health required to exit cell (i, j). Remember we are moving from bottom to up; thus, only two options are available: (i+1, j) and (i, j+1). Of course, we'll pick the cell where we can complete the rest of his journey with fewer health. As a result, we have: 

MINIMUM_HEALTH_ON_EXIT = min(DP[i + 1][j], DP[i][j + 1]) 

Now that we know how to calculate MINIMUM_HEALTH_ON_EXIT, we must populate the table DP[][] in order to obtain the solution in DP[0][0].

Also, we have to reduce the health required to stay in the current cell so that we will store our probable answer in ‘VAL’.

VAL = MINIMUM_HEALTH_ON_EXIT – DUNGEON[i][j]

How do you calculate DP[i][j]?

Hence the following is a representation of the value of DP[i][j].

DP[i][j] = max(VAL, 1)

Now let's look at the implementation of the above approach.

Code

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int calculateMinimumHP(vector<vector < int>> &dungeon)
{
    int r = dungeon.size();
    // Base case: If the size of the dungeon is zero.
    if (r == 0)
        return 0;

    int c = c = dungeon[0].size();

    // We will create a DP table and initialize it to INT_MAX.
    vector<vector < int>> dp(r + 1, vector<int> (c + 1, INT_MAX));

    // Initializing the cell to the bottom and right of the princess' cell with value 1(As minimum 1 energy is needed).
    dp[r - 1][c] = 1;
    dp[r][c - 1] = 1;

    // Looping over DP table.
    for (int i = r - 1; i >= 0; i--)
    {
        for (int j = c - 1; j >= 0; j--)
        {
            // (Minimum healthvalue to land on next) - (health needed to stay)
            int val = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];

            // Now answer would be either 1 or 'VAL' that we calculated.
            dp[i][j] = max(1, val);
        }
    }

    // Returning the answer that is stored in DP[0][0].
    return dp[0][0];
}

int main()
{
    // Taking Input.
    int m, n;
    cout << "Enter number of rows: ";
    cin >> m;
    cout << "Enter number of columns: ";
    cin >> n;
    cout << "Enter elements of dungeon: " << endl;
    vector<vector<int>> dungeon(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> dungeon[i][j];
        }
    }

    cout << "Minimum energy required in the beginning is: " << calculateMinimumHP(dungeon);
    return 0;
}

Input

Enter number of rows: 3
Enter number of columns: 3
Enter elements of dungeon: 
-1 -3 3
-3 -4 4
10 20 -2

Output

Minimum energy required in the beginning is: 5

Time Complexity

O(M * N), where ‘M’ is the number of rows of the dungeon matrix, and ‘N’ is the number of columns.

As we are using two nested loops first one till ‘M’ and the other one till ‘N’, thus the time complexity is O(M * N)

Space Complexity

O(M * N), where ‘M’ is the number of rows of the dungeon matrix, and ‘N’ is the number of columns.

As we are using a DP array of size M * N.

Key Takeaways

We first saw the brute force approach to solve the problem. We gradually build the recursive relation and saw how overlapping subproblems can be dealt with using dynamic programming.

You must be thrilled to learn the idea and intuition to approach similar DP problems. But learning never stops, and a good coder should never stop practicing. So, head over to our practice platform CodeStudio to practice top problems and many more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes