凸多邊形的三角形分割以及二維陣列與整數最大值的使用

今天練習的題目是 1039. Minimum Score Triangulation of Polygon，第一次遇到這種 DP 類型，後來想通後，發現解題辦法不外乎兩種。

一種是由上而下，透過記憶跟遞迴來處理，效率較差，寫成 C++ 會像是這樣：

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        array<array<int, 50>, 50> memo{};
        function<int(int, int)> dp = [&](int i, int j) -> int {
        	if (i + 2 > j)
                return 0;
            if (!memo[i][j]) {
                if (i + 2 == j)
                    return memo[i][j] =
                               values[i] * values[i + 1] * values[i + 2];
                int score = numeric_limits<int>::max();
                int product = values[i] * values[j];
                for (int k = i + 1; k < j; ++k)
                    score =
                        min(score, product * values[k] + dp(i, k) + dp(k, j));
                memo[i][j] = score;
            }
            return memo[i][j];
        };
        return dp(0, n - 1);
    }
};

另一種是由下而上，透過疊代來處理，效率較好，寫成 C++ 會像是這樣：

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
    	int n = values.size();
        array<array<int, 50>, 50> dp{};
        for (int d = 2; d < n; ++d) {
            for (int i = 0; i + d < n; ++i) {
                int j = i + d;
                int score = numeric_limits<int>::max();
                int product = values[i] * values[j];
                for (int k = i + 1; k < j; ++k)
                    score =
                        min(score, product * values[k] + dp[i][k] + dp[k][j]);
                dp[i][j] = score;
            }
        }
        return dp[0][n - 1];
    }
};

用疊代的方法寫成 Python3 會像這樣：

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for d in range(2, n):
            for i in range(n - d):
                j = i + d
                score = float("inf")
                product = values[i] * values[j]
                for k in range(i + 1, j):
                    score = min(score, product * values[k] + dp[i][k] + dp[k][j])
                dp[i][j] = score
        return dp[0][n - 1]

用疊代的方法寫成 Go 會像這樣：

func minScoreTriangulation(values []int) int {
	n := len(values)
	dp := make([][]int, n)
	for i := range n {
		dp[i] = make([]int, n)
	}
	for d := 2; d < n; d++ {
		for i := range n - d {
			j := i + d
			score := math.MaxInt
			product := values[i] * values[j]
			for k := i + 1; k < j; k++ {
				score = min(score, product*values[k]+dp[i][k]+dp[k][j])
			}
			dp[i][j] = score
		}
	}
	return dp[0][n-1]
}

用疊代的方法寫成 Rust 會像這樣：

impl Solution {
    pub fn min_score_triangulation(values: Vec<i32>) -> i32 {
    	let n = values.len();
        let mut dp = vec![vec![0; n]; n];
        for d in 2..n {
            for i in 0..(n - d) {
                let j = i + d;
                let mut score = i32::MAX;
                let mut product = values[i] * values[j];
                for k in (i + 1)..j {
                    score = score.min(product*values[k]+dp[i][k]+dp[k][j]);
                }
                dp[i][j] = score;
            }
        }
        dp[0][n-1]
    }
}

另外值得一提的是 Rust 目前 1.90.0 還沒有支援 nested recursive function call，雖然上面沒有全部寫出來，但是 C++, Python3, Go 都有支援，如果這題要用 Rust 寫記憶跟遞迴會蠻麻煩的，反正效率也比較差，就寫個 C++ 意思意思一下就好了。