Java AC solution with dynamic programming


  • 0
    public class Solution {
        public int minTransfers(int[][] transactions) {
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int[] tran : transactions)
            {
                map.put(tran[0],map.getOrDefault(tran[0],0)-tran[2]);
                map.put(tran[1],map.getOrDefault(tran[1],0)+tran[2]);
            }
            ArrayList<Integer> arr = new ArrayList<>();
            for(int val : map.values())
            {
                if(val!=0)
                {
                    arr.add(val);
                }
            }
            HashMap<Integer,Integer> memo = new HashMap<Integer,Integer>();
            return dp(arr,memo);
        }
        
        public int dp(ArrayList<Integer> arr,HashMap<Integer,Integer> memo)
        {
            if(arr.size()==0)
            {
                return 0;
            }
            if(memo.containsKey(arr.hashCode())) return memo.get(arr.hashCode());
            int first = arr.get(0);
            arr.remove(0);
            int min=Integer.MAX_VALUE;
            for(int i=0;i<arr.size();i++)
            {
                int other = arr.get(i);
                if(first*other>0) continue;
                if(first+other==0)
                {
                    arr.remove(i);
                    min=Math.min(min,dp(arr,memo)+1);
                    arr.add(i,other);
                }
                else
                {
                    arr.set(i,first+other);
                    min=Math.min(min,dp(arr,memo)+1);
                    arr.set(i,other);
                }
              
            }
            arr.add(0,first);
            memo.put(arr.hashCode(),min);
            return min;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.