Java DP approach (iterative)


  • 0
    S
    //1. process input, let it be a list of strings, every string in the list is a number. Let's call the list "numbers". We need another list called operators, each element is either +, -, or *.
    //2. dp[i][j] should be a List<Integer>, representing the result of all possible result from numbers i to numbers j, with the corresponding operators connecting them.
    //3. dp[i][i] should be the number itself.
    //4. dp[i][j]= dp[i][k] cross operate dp[k][j] for every k in between i and j
    //5. return dp[0][last]
    
    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            //1. process input
            List<Integer> numbers = new ArrayList<>();
            List<Character> operators = new ArrayList<>();
            
            int start = 0, end = 0;
            while(end < input.length()){
                char c = input.charAt(end);
                if(c == '+' || c == '-' || c== '*'){
                    numbers.add(Integer.parseInt(input.substring(start, end)));
                    operators.add(c);
                    end ++;
                    start = end;
                }else{
                    end++;
                }
            }
            
            //add the last number.
            numbers.add(Integer.parseInt(input.substring(start, end)));
            
            //2. initialize dp
            int size = numbers.size();
            //I wanted to create dp as an array, something like List<Integer>[][], but java does not allow me to do it.
            List<List<List<Integer>>> dp = new ArrayList<>();
            for(int i = 0; i < size; i++){
                dp.add(new ArrayList<>());
                for(int j = 0; j < size; j++){
                    dp.get(i).add(new ArrayList<Integer>(size));
                }
                
                dp.get(i).get(i).add(numbers.get(i));
            }
            
            
            
            
            //3. induction
            for(int i = size - 1; i >= 0; i--){
                for(int j = i + 1; j < size; j++){
                   for(int k = i; k < j; k ++){
                       List<Integer> left = dp.get(i).get(k);
                       List<Integer> right = dp.get(k+1).get(j);
                       char op = operators.get(k);
                       List<Integer> compute = crossCompute(left, right, op);
                       dp.get(i).get(j).addAll(compute);
                   }
                
                }
            }
            
            return dp.get(0).get(size-1);
    
            
        }
        
        
        
        private List<Integer> crossCompute(List<Integer> list1, List<Integer> list2, char operator){
            List<Integer> result = new ArrayList<>();
           
            for(int n1 : list1){
                for(int n2 : list2){
                    if(operator == '-'){
                        result.add(n1-n2);
                    }else if(operator == '+'){
                        result.add(n1+n2);
                    }else{
                        result.add(n1*n2);
                    }
                }
            }
            
            return result;
    
        }
    }```

Log in to reply
 

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