2023-08-26：请用go语言编写。开心一下的智力题：
有一个村庄，一共250人，
每一个村民要么一定说谎，要么只说真话，
村里有A、B、C、D四个球队，且每个村民只会喜欢其中的一支球队，
但是说谎者会不告知真实喜好，而且会说是另外三支球队的支持者。
访问所有的村民之后，得到的访谈结果如下 :
A的支持者有90，
B的支持者有100，
C的支持者有80，
D的支持者有80。
问村里有多少个说谎者。
下面是正式题 :
你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，
其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。
假设将多边形 剖分 为 n - 2 个三角形。
对于每个三角形，该三角形的值是顶点标记的乘积，
三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。
返回 多边形进行三角剖分后可以得到的最低分 。
输入：values = [1,2,3]。
输出：6。
解释：多边形已经三角化，唯一三角形的分数为 6。
来自左程云。
答案2023-08-26：
大体过程如下：
1.在main函数中，定义一个整数数组values表示每个顶点的值。
2.调用minScoreTriangulation函数，传入values数组，并将返回的最低分数打印出来。
3.在minScoreTriangulation函数中，首先获取顶点数量N，然后创建一个二维切片dp作为动态规划的缓存。
4.初始化dp切片为-1。
5.返回调用递归函数f，传入values、起始位置0、结束位置N-1以及dp切片。
6.在f函数中，首先处理递归终止条件，如果起始位置i大于等于结束位置j-1，返回0，表示无法构成三角形。
7.如果在缓存中存在dp[i][j]的结果，则直接返回结果。
8.初始化ans变量为math.MaxInt32，用于存储最小的分数。
9.对于所有的m从i+1到j-1，遍历所有可能的分割点。
10.对于每个分割点m，计算分割两部分的分数和，并取最小值。
11.更新ans为当前最小值。
12.将ans存入缓存dp[i][j]中。
13.返回ans作为结果。
总的时间复杂度为O(N^3)，因为有三层嵌套循环，每层循环的次数最大为N。
总的空间复杂度为O(N^2)，因为需要创建一个二维切片dp作为缓存，其大小为N*N。
go完整代码如下：
package main
import (
"fmt"
"math"
)
func main() {
values := []int{1, 2, 3}
result := minScoreTriangulation(values)
fmt.Println(result)
}
func minScoreTriangulation(values []int) int {
N := len(values)
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, N)
for j := 0; j < N; j++ {
dp[i][j] = -1
}
}
return f(values, 0, N-1, dp)
}
func f(values []int, i int, j int, dp [][]int) int {
if i >= j-1 {
return 0
}
if dp[i][j] != -1 {
return dp[i][j]
}
ans := math.MaxInt32
for m := i + 1; m < j; m++ {
ans = int(math.Min(float64(ans), float64(f(values, i, m, dp)+f(values, m, j, dp)+values[i]*values[m]*values[j])))
}
dp[i][j] = ans
return ans
}
rust语言完整代码如下：
fn min_score_triangulation(values: Vec<i32>) -> i32 {
let mut dp = vec![vec![-1; values.len()]; values.len()];
return f(&values, 0, values.len() - 1, &mut dp);
}
// values[i...j]范围上这些点，要分解成多个三角形
// 三角形一个端点是values[i]，另一个端点是values[j]
// 那么第三个点在i+1....j-1之间选
// 比如选了m点 : i......m.......j
// 当前获得的分数为values[i] * values[m] * values[j]
// 接下来，i.....m去分解三角形、m.....j去分解三角形
fn f(values: &Vec<i32>, i: usize, j: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
if i >= j - 1 {
// 不够三个点，不会有得分
return 0;
}
if dp[i][j] != -1 {
// 缓存的答案
// 如果命中直接返回
// 看体系学习班，动态规划的章节
return dp[i][j];
}
let mut ans = std::i32::MAX;
for m in i + 1..j {
ans = std::cmp::min(
ans,
f(values, i, m, dp) + f(values, m, j, dp) + values[i] * values[m] * values[j],
);
}
dp[i][j] = ans;
return ans;
}
fn main() {
let values = vec![1, 2, 3];
let result = min_score_triangulation(values);
println!("Result: {}", result);
}
c++完整代码如下：
#include <iostream>
#include <vector>
#include <climits>
int f(std::vector<int>& values, int i, int j, std::vector<std::vector<int>>& dp);
int minScoreTriangulation(std::vector<int>& values) {
int n = values.size();
std::vector<std::vector<int>> dp(n, std::vector<int>(n, -1));
return f(values, 0, n - 1, dp);
}
int f(std::vector<int>& values, int i, int j, std::vector<std::vector<int>>& dp) {
if (i >= j - 1) {
// 不够三个点，不会有得分
return 0;
}
if (dp[i][j] != -1) {
// 缓存的答案
// 如果命中直接返回
// 看体系学习班，动态规划的章节
return dp[i][j];
}
int ans = INT_MAX;
for (int m = i + 1; m < j; m++) {
ans = std::min(ans, f(values, i, m, dp) + f(values, m, j, dp) + values[i] * values[m] * values[j]);
}
dp[i][j] = ans;
return ans;
}
int main() {
std::vector<int> values = { 1, 2, 3 };
int result = minScoreTriangulation(values);
std::cout << "Result: " << result << std::endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#include <limits.h>
int min(int a, int b) {
return (a < b) ? a : b;
}
int f(int* values, int i, int j, int dp[][100]) {
if (i >= j - 1) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int ans = INT_MAX;
for (int m = i + 1; m < j; m++) {
ans = min(ans, f(values, i, m, dp) + f(values, m, j, dp) + values[i] * values[m] * values[j]);
}
dp[i][j] = ans;
return ans;
}
int minScoreTriangulation(int* values, int valuesSize) {
int dp[100][100];
for (int i = 0; i < valuesSize; i++) {
for (int j = 0; j < valuesSize; j++) {
dp[i][j] = -1;
}
}
return f(values, 0, valuesSize - 1, dp);
}
int main() {
int values[] = { 1, 2, 3 };
int valuesSize = sizeof(values) / sizeof(values[0]);
int result = minScoreTriangulation(values, valuesSize);
printf("Result: %d\n", result);
return 0;
}