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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接