区间 DP

动态规划

说明

按区间长度递增计算答案；下例在每个切点合并两段得到矩阵链最少乘法次数。

分析

矩阵链的子问题由连续区间 [l,r] 决定；只有更短区间已经算出，才能枚举切点 k 并组合左右最优代价。按区间长度递增填表满足这一依赖顺序。

图解推演

维度 [10,30,5,60] 表示 A 为 10×30、B 为 30×5、C 为 5×60。(AB)C 代价 1500+3000=4500，A(BC) 代价 9000+18000=27000。枚举切点时必须加上左右子问题代价及最后一次乘法代价，不能只比较中间矩阵尺寸。

查看图表代码

适用前提与边界

矩阵维度数组要满足相邻矩阵可以相乘，算法时间 O(n³)。

示例输入与调用

fmt.Println(MatrixChain([]int{10, 30, 5, 60}))

运行输出

4500

完整 Go 示例

package main

import "fmt"

func MatrixChain(dims []int) int {
	n := len(dims) - 1
	if n <= 0 {
		return 0
	}
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for length := 2; length <= n; length++ {
		for l := 0; l+length <= n; l++ {
			r := l + length - 1
			dp[l][r] = int(^uint(0) >> 1)
			for k := l; k < r; k++ {
				cost := dp[l][k] + dp[k+1][r] + dims[l]*dims[k+1]*dims[r+1]
				dp[l][r] = min(dp[l][r], cost)
			}
		}
	}
	return dp[0][n-1]
}

func main() {
	fmt.Println(MatrixChain([]int{10, 30, 5, 60}))
}