# Java dp solution

• ``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> nums = new ArrayList<Integer>();
List<Character> ops = new ArrayList<Character>();
decode(input,nums,ops);
List<Integer> ans = new ArrayList<Integer>();
int len = nums.size();
List<List<List<Integer>>> dp = new ArrayList<List<List<Integer>>>();
for(int i=0;i<len;i++)
for(int j=0;j<len;j++)
for(int dist=1;dist<len;dist++){
//dp[begin][end] = dp[begin][k] ops[k] dp[k+1[end];(begin<=k<end)
for(int begin=0;begin<len-dist;begin++){
int end = begin+dist;
for(int k=begin;k<end;k++){
for(int i=0;i<dp.get(begin).get(k).size();i++)
for(int j=0;j<dp.get(k+1).get(end).size();j++)
}
}
}
return dp.get(0).get(len-1);
}
private int compute(Integer num1, Character op, Integer num2){
switch (op){
case '+':
return num1+num2;

case '-':
return num1-num2;

case '*':
return num1*num2;

case '/':
return num1/num2;

default:
return 0;
}
}
private void decode(String input, List<Integer> nums, List<Character> ops){
int i=0,len = input.length();
while(i<len){
int cur = 0;
while(i<len){
char c = input.charAt(i);
if(c < '0' || c> '9'){
break;
}
cur = cur *10 + c - '0';
i++;
}
if(i<len){
i++;
}
}
}
}``````

• Same, but with `dp` as array and spaces:

``````public List<Integer> diffWaysToCompute(String input) {
List<Integer> nums = new ArrayList<>();
List<Character> ops = new ArrayList<>();
decode(input, nums, ops);
int len = nums.size();
List<Integer>[][] dp = new ArrayList[len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
dp[i][j] = new ArrayList<>();
}
}
for (int i = 0; i < len; i++) {
}
for (int dist = 1; dist < len; dist++) {
for (int begin = 0; begin < len - dist; begin++) {
int end = begin + dist;
// dp[begin][end] = dp[begin][k] ops[k] dp[k+1][end] (begin <= k < end)
for (int k = begin; k < end; k++) {
for (int left : dp[begin][k]) {
for (int right : dp[k + 1][end]) {
}
}
}
}
}
return dp[0][len - 1];
}
private int compute(int num1, char op, int num2) {
switch (op) {
case '+': return num1 + num2;
case '-': return num1 - num2;
case '*': return num1 * num2;
case '/': return num1 / num2;
default: return 0;
}
}
private void decode(String input, List<Integer> nums, List<Character> ops) {
int i = 0, len = input.length();
while (i < len) {
int num = 0;
while (i < len) {
char c = input.charAt(i);
if (c < '0' || c > '9') {
break;
}
num = num * 10 + c - '0';
i++;
}