Dungeon Princess

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.dynamic_programming;

import java.util.*;

/ * Problem: Dungeon Princess * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Dungeon Princess (Minimum Initial Health) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a grid where: * - Negative numbers decrease health. * - Positive numbers increase health. * Find min initial health to go from (0,0) to (N-1, M-1) such that health > 0 at all times. * * --------------------- * 2. Logical Breakdown (Reverse DP) * --------------------- * Why standard Forward DP fails: * In standard Min Path Sum, we just care about the total sum. Here, the sequence matters * (we can't dip below 1 at any intermediate step). * * Strategy: Start from the Destination (Bottom-Right) back to Source (Top-Left). * Let dp[i][j] be the min health needed AT cell (i, j) to safely reach the princess. * * Recurrence: * At cell (i, j), we can go Right or Down. We want the path that requires less health. * min_health_needed_next = min(dp[i+1][j], dp[i][j+1]) * * Current requirement: * dp[i][j] = min_health_needed_next - dungeon[i][j] * * Constraint: * If dungeon[i][j] is a huge power-up, the math might say we need negative health. * But we must have at least 1 HP to be alive. * So, dp[i][j] = max(1, dp[i][j]) * * Base Case (Princess Room): * dp[N-1][M-1] = max(1, 1 - dungeon[N-1][M-1]) * * --------------------- * 3. Complexity * --------------------- * Time: O(N * M) * Space: O(N * M) * * ============================================================================================ */ public class DungeonPrincess { public int solve(int A) { // TODO: Implement solution return 0; }

public int calculateMinimumHP(int[][] dungeon) {
    return 1;
}

}