Dungeon Game

An m x n dungeon contains negative, zero, and positive integers. A negative value decreases health, zero leaves health unchanged, and a positive value increases health.

A knight starts in the top-left room and must reach the princess in the bottom-right room. Only rightward and downward moves are allowed. Health must remain strictly greater than 0 after every room, including the starting and destination rooms. Return the minimum positive initial health required for a valid journey.

Recursion

Every room offers at most two choices: move right or move down. A nearby reward can still lead toward severe damage, so the best route depends on the complete remaining journey. Planning backward turns the journey into a simple entry requirement for each room.

State solve(row, col) stores the minimum health needed upon entering room (row, col) and safely reaching the princess. Recursion fits because every room leads to the same smaller problem from the right or downward neighbor. The first helper call uses solve(0, 0) because every valid journey starts at the dungeon entrance.

Algorithm

• Begin with solve(row, col) as the minimum health required upon entering room (row, col), so every call describes the same survival goal.

• Return a large value for an out-of-bounds position because an invalid move must never become the cheaper continuation.

• Calculate the destination requirement as max(1, 1 - dungeon[row][col]) because at least 1 health must remain after the final room.

• Explore the downward and rightward states because every valid next move belongs to one of the two allowed directions.

• Select the smaller future requirement because the knight may follow whichever valid route needs less entry health.

• Subtract the current room value from the selected requirement because damage raises the entry need while healing lowers the entry need.

• Return at least 1 for every state because health equal to 0 already violates the survival rule.

Dry Run

Solution

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2^{(M + N)}), where M is the number of rows and N is the number of columns, because each recursive state can branch into at most two choices across a maximum path length of M + N - 1.

Space Complexity: O(M + N), because the recursion stack can store at most one active path from the top-left to the bottom-right cell.

Memoization

Direct recursion asks for the same room requirement through many different paths. The state depends only on row and col, so every repeated call produces the same answer.

A 2D array named dp stores each calculated requirement. The original backward recurrence remains unchanged; a saved value simply avoids repeated exploration.

Algorithm

• Begin with a dp matrix filled with -1 so every untouched room clearly represents an uncalculated requirement.

• Keep solve(row, col) as the minimum entry health for one room because memoization must preserve the recursive state meaning.

• Return a large value for an out-of-bounds position because an invalid direction must never win the minimum comparison.

• Reuse a saved dp[row][col] value whenever available because many paths request the same room requirement.

• Store the destination requirement once as max(1, 1 - dungeon[row][col]) because the final room must leave at least 1 health.

• Compare the downward and rightward requirements because the cheaper valid continuation determines the best route from the current room.

• Save max(1, nextNeeded - dungeon[row][col]) in dp and return the value so later calls avoid the same exploration.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because each of the M × N room states is computed once and each state checks two constant-time transitions.

Space Complexity: O(M × N), because the dp matrix stores M × N values, while the O(M + N) recursion stack is dominated by the O(M × N) DP storage.

Tabulation

Memoization already identifies every required state, but recursion is unnecessary once the dependency order becomes visible. Each room depends on the room below and the room to the right, so the table can be filled from bottom-right to top-left.

The same state meaning and recurrence are retained. The destination is filled first, followed by the last row, the last column, and all remaining rooms.

Algorithm

• Begin with a 2D array named dp so dp[row][col] can keep the minimum health required upon entering one room.

• Initialize the destination with max(1, 1 - dungeon[rows - 1][cols - 1]) because the last room must leave at least 1 health.

• Fill the last row from right to left because every room on the bottom edge can continue only toward the right.

• Fill the last column from bottom to top because every room on the right edge can continue only downward.

• Visit all remaining rooms from bottom to top and right to left so both successor requirements are ready before each calculation.

• Select the smaller right or down requirement and subtract the current room value because the chosen continuation controls the needed entry health.

• Return dp[0][0] because the top-left state represents the minimum health required at the dungeon entrance.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because the reverse traversal processes every room once with constant work.

Space Complexity: O(M × N), because the 2D dp matrix stores one requirement for every room, while the iterative approach uses no recursion stack.

Space Optimization

Tabulation needs only the next row and the already calculated right neighbor in the current row. Older rows never participate in a later transition, so the full matrix can be replaced by two one-dimensional rows.

nextRow[col] represents dp[row + 1][col], while currentRow[col + 1] represents dp[row][col + 1]. A current value is calculated from both entries, saved at currentRow[col], and the completed currentRow becomes nextRow only after the entire row has been processed.

Algorithm

• Begin with nextRow and currentRow filled with a large value so missing neighbors naturally lose every minimum comparison.

• Process rows from bottom to top and columns from right to left because every transition needs the completed down and right states.

• Assign max(1, 1 - dungeon[row][col]) to the destination because the final room must still leave positive health.

• Keep a large value for every unavailable neighbor because grid boundaries must never become valid route choices.

• Calculate current from the smaller down or right requirement because only the cheaper continuation belongs in the current state.

• Store current in currentRow[col] so the next cell on the left can use the new right-neighbor requirement.

• Shift the completed currentRow into nextRow, then return nextRow[0] after the top row because older rows cannot affect later transitions.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because the rolling-row traversal processes every room once with constant work.

Space Complexity: O(N), because two arrays of N columns store only the current row and the next row.