This question is the variation of Stone Game. Let’s start with the brute-force approach. Assume n = piles.length. If we enumerate all possible paths that a player choose either the start or the end stones in the array, players switch between different layers. Each path has a length of n. For each path, we can track the sum scores of two players. At the botom of the decision tree, we compare two player's scores:
Let’s start with the brute-force approach. Assume m = dungeon.length and n = dungeon[0].length. If we enumerate all possible paths from the top-left to the bottom-right cell, at each step we have two choices: move right or move down. Each path has a length of m + n − 1. For each path, we can track the minimum health encountered along the way to determine the minimum initial health required to survive that path. The time complexity is . Given the constraints 1 <= m, n <= 200, this brute-force approach is computationally infeasible and will result in a TLE.
This is an unbounded knapsack problem, meaning there is no upper limit on how many copies of each item (coin) can be used. In general, knapsack-type problems are well suited for dynamic programming. If you are not familiar with DP, you may want to take a look at my website, where I provide a detailed explanation of the core ideas.
