Problem

In the XX game, there is a fatigue system represented by non-negative integers, allowing players to explore dungeons by using a certain amount of fatigue. Each dungeon requires a “minimum required fatigue” to start exploring and consumes a certain amount of “fatigue” upon completion. For example, to explore a dungeon with a “minimum required fatigue” of 80 and a “consumption fatigue” of 20, a player’s current remaining fatigue must be at least 80, and it will decrease by 20 after exploring the dungeon. The game features multiple dungeons that can be explored once a day, and a player aims to maximize the number of dungeons explored in a day. Given the player’s current fatigue k and a 2D array dungeons that contains the “minimum required fatigue” and “consumption fatigue” for each dungeon, implement a function solution to return the maximum number of dungeons a player can explore.

Constraints

• k is a natural number between 1 and 5,000.
• The length of the dungeons array (number of dungeons) is between 1 and 8.
• Each row in the dungeons array has 2 elements representing the [“minimum required fatigue”, “consumption fatigue”] for each dungeon.
• “Minimum required fatigue” is always equal to or greater than “consumption fatigue”.
• Both “minimum required fatigue” and “consumption fatigue” range from 1 to 1,000.
• Different dungeons can have the same [“minimum required fatigue”, “consumption fatigue”] values.

Example

Explanation of Examples

In the example, the player starts with a fatigue of 80. If the player explores the dungeons in the sequence of the first → third → second, here’s how it goes:

• Initial fatigue is 80, matching the first dungeon’s “minimum required fatigue” of 80. After exploring, the remaining fatigue is 60.
• The remaining fatigue is 60, which is enough for the third dungeon’s “minimum required fatigue” of 30. After exploring, the remaining fatigue is 50.
• The remaining fatigue is 50, matching the second dungeon’s “minimum required fatigue” of 50. After exploring, the remaining fatigue is 10. Thus, in this scenario, the player can explore all three dungeons, making the maximum number of dungeons explored 3.

How to Approach?

Step1: Initialize variables in loop

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.util.*;

class Solution {
    private int answer = 0;

    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        exploreDungeons(k, dungeons, visited, 0);
        return answer;
    }

    private void exploreDungeons(int fatigue, int[][] dungeons, boolean[] visited, int count){
        for(int i=0; i<dungeons.length; i++){
            if (!visited[i] && dungeons[i][0] <= fatigue) {
                // Mark the dungeon as visited
                visited[i] = true;
                // Recursively try the next dungeons with the updated fatigue and count
                exploreDungeons(fatigue - dungeons[i][1], dungeons, visited, count + 1);
                // Backtrack: unmark the dungeon as visited for the next iterations
                visited[i] = false;
        }
        answer = Math.max(answer, count);
        }
    }   
}