Multiplication Puzzle（区间dp）

题目链接

动态转移方程 ： dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + num[i] * num[j] * num[k])
先求出长度较短的子问题的解，以自底向上的方法求出大问题的最优解
长度从 3 开始设置，每次求出从[l, l + len - 1] 内的最优解，最终求出答案

#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int M = 110;
int num[M], dp[M][M]; 
// dp[i][j] 表示[i, j] 范围内 最小的结果
int main() {
	int n;
	scanf("%d", &n);
	memset(dp, INF, sizeof(dp));
	for (int i = 1; i <= n; ++i) scanf("%d", &num[i]);
	for (int i = 1; i <= n; ++i) {
		dp[i][i] = 0;
		dp[i - 1][i] = dp[i][i + 1] = 0;
		// len 为1 或者 2时设置为0
	}
	for (int len = 3; len <= n; ++len) {
		for (int l = 1; l + len - 1 <= n; ++l) {
			int r = l + len - 1;
			for (int k = l + 1; k < r; ++k) {
				dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + num[l] * num[r] * num[k]);
			}
		}
	}
	printf("%d", dp[1][n]);
	return 0;
}