递归，动态规划，2 解法求解《241. 为运算表达式设计优先级》
例题
241. 为运算表达式设计优先级
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
示例 1：
输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2
答案
递归
var diffWaysToCompute = function(expression) {
const n = expression.length, h = Array.from({length: n}, _ => Array.from({length: n}, _ => [])), a = []
let t = ''
for (let i = 0; i < n; i++) {
const code = expression.charCodeAt(i)
if (code >= 48 && code <= 57) t += expression[i]
else {
if (t) a.push(t), t = ''
a.push(expression[i])
}
}
if (t) a.push(t)
const d = (l, r) => {
if (h[l][r].length === 0) {
if (l == r) h[l][r].push(a[l])
for (let i = l; i < r; i += 2) {
const ls = d(l, i), ln = ls.length
const rs = d(i + 2, r), rn = rs.length
for (let j = 0; j < ln; j++) {
for (let k = 0; k < rn; k++) {
if (a[i + 1] === '+') h[l][r].push(+ls[j] + +rs[k])
else if (a[i + 1] === '-') h[l][r].push(ls[j] - rs[k])
else h[l][r].push(ls[j] * rs[k])
}
}
}
}
return h[l][r]
}
return d(0, a.length - 1)
};func diffWaysToCompute(expression string) []int {
n, t, a := len(expression), -1, []int{}
for _, c := range expression {
if (c >= 48) {
if t >= 0 {
t = t * 10 + int(c) - 48
} else {
t = int(c) - 48
}
} else {
if t >= 0 {
a = append(a, t)
t = -1
}
a = append(a, int(c))
}
}
if t >= 0 {
a = append(a, t)
}
an := len(a)
h := make([][][]int, n)
for i := 0; i < n; i++ {
h[i] = make([][]int, n)
for j := 0; j < n; j++ {
h[i][j] = []int{}
}
}
var d func(l, r int) []int
d = func(l, r int) []int {
if len(h[l][r]) == 0 {
if l == r {
h[l][r] = append(h[l][r], a[l])
} else {
for i := l; i < r; i += 2 {
ls, rs := d(l, i), d(i + 2, r)
for _, lv := range ls {
for _, rv := range rs {
if a[i + 1] == 43 {
h[l][r] = append(h[l][r], lv + rv)
} else if a[i + 1] == 45 {
h[l][r] = append(h[l][r], lv - rv)
} else {
h[l][r] = append(h[l][r], lv * rv)
}
}
}
}
}
}
return h[l][r]
}
return d(0, an - 1)
}动态规划
var diffWaysToCompute = function(expression) {
const n = expression.length, dp = Array.from({length: n}, _ => Array.from({length: n}, _ => [])), a = []
let t = ''
for (let i = 0; i < n; i++) {
const code = expression.charCodeAt(i)
if (code >= 48 && code <= 57) t += expression[i]
else {
if (t) a.push(t), t = ''
a.push(expression[i])
}
}
if (t) a.push(t)
const an = a.length
for (let len = 1; len <= an; len += 2) {
for (let l = 0; l + len <= an; l += 2) {
const r = l + len - 1
if (l === r) dp[l][r].push(+a[l])
else {
for (let i = l; i < r; i += 2) {
for (const lv of dp[l][i]) {
for (const lr of dp[i + 2][r]) {
if (a[i + 1] === '+') dp[l][r].push(lv + lr)
else if (a[i + 1] === '-') dp[l][r].push(lv - lr)
else dp[l][r].push(lv * lr)
}
}
}
}
}
}
return dp[0][an - 1]
};class Solution {
public List<Integer> diffWaysToCompute(String expression) {
int n = expression.length();
int t = -1;
List<Integer> a = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if (expression.charAt(i) >= 48) t = (t > -1 ? t * 10 : 0) + expression.charAt(i) - 48;
else {
if (t != -1) {
a.add(t);
t = -1;
}
a.add(+expression.charAt(i));
}
}
if (t != -1) a.add(t);
int an = a.size();
List<Integer>[][] dp = new List[an][an];
for (int i = 0; i < an; i++) {
for (int j = 0; j < an; j++) {
dp[i][j] = new ArrayList<Integer>();
}
}
for (int len = 1; len <= an; len += 2) {
for (int l = 0; l + len <= an; l += 2) {
int r = l + len - 1;
if (l == r) dp[l][r].add(a.get(l));
else {
for (int i = l; i < r; i += 2) {
for (Integer lv : dp[l][i]) {
for (Integer rv : dp[i + 2][r]) {
if (a.get(i + 1) == 43) dp[l][r].add(lv + rv);
else if (a.get(i + 1) == 45) dp[l][r].add(lv - rv);
else dp[l][r].add(lv * rv);
}
}
}
}
}
}
return dp[0][an - 1];
}
}