Divide: 把问题从较大的规模分解为最小的规模
根据这个思路, 很容易就改写为DP
min = findMin(nums, pre, i, k, cache) + findMin(nums, pre, k + 1, j, cache) + pre[j + 1] - pre[i];
dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j + 1] - pre[i];
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
//求前缀和
int[] pre = new int[n + 1];
for (int i = 1; i < pre.length; i++) {
pre[i] = pre[i - 1] + nums[i - 1];
}
//记忆化
int[][] cache = new int[nums.length][nums.length];
for (int[] row : cache) {
Arrays.fill(row, -1);
}
int min = findMin(nums, pre, 0, nums.length - 1, cache);
System.out.println(min);
}
//把从 0 到 n 的问题分解为从 i 到 j 的问题,直到i == j
public static int findMin(int[] nums, int[] pre, int i, int j, int[][] cache) {
//只有一堆,花费为0
if (i == j) {
return 0;
}
if (cache[i][j] != -1) {
return cache[i][j];
}
int min = Integer.MAX_VALUE;
//把 i 到 j 再分解为 i 到 k 和 k + 1 到 j
for (int k = i; k < j; k++) {
int res = findMin(nums, pre, i, k, cache) + findMin(nums, pre, k + 1, j, cache) + pre[j + 1] - pre[i];
min = Math.min(min, res);
}
cache[i][j] = min;
return min;
}
}