# Java DP approach (iterative)

• ``````//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== '*'){
end ++;
start = end;
}else{
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++){
for(int j = 0; j < size; j++){
}

}

//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);
}

}
}

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 == '-'){
}else if(operator == '+'){