Untitled

class Solution {
    public boolean solve(int[][] dungeon,int i,int j,int health,HashMap<String,Boolean>map){
        if(health<=0)
         return false; 
        
        if(i==dungeon.length-1 && j==dungeon[0].length-1)
         return health+dungeon[i][j]>0;

        if(i>=dungeon.length || j>=dungeon[0].length)
         return false;

        String key = i+","+j+","+health;
        if(map.containsKey(key))
         return map.get(key);
        
        boolean ans1=false,ans2=false;
        ans1 = solve(dungeon,i+1,j,health+dungeon[i][j],map);
        ans2 = solve(dungeon,i,j+1,health+dungeon[i][j],map);

        map.put(key, ans1 || ans2);

        return ans1 || ans2;
    }

    public int calculateMinimumHP(int[][] dungeon) {
        int n=dungeon.length;
        int m=dungeon[0].length;
        int low=1,high=200000;
        int ans=0;

        while(low<=high){
            int mid = low+(high-low)/2;

            HashMap<String,Boolean>map=new HashMap<>();

            if(solve(dungeon,0,0,mid,map)){
                ans=mid;
                high=mid-1;
            }
            else
             low=mid+1;
        }

        return ans;
    }
}