今天練習的題目是 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++ 意思意思一下就好了。
