2023-08-26：請用go語言編寫。開心一下的智力題： 有一個村莊，一共250人， 每一個村
2023-08-26：請用go語言編寫。開心一下的智力題：
有一個村莊，一共250人，
每一個村民要么一定說謊，要么只說真話，
村里有A、B、C、D四個球隊(duì)，且每個村民只會喜歡其中的一支球隊(duì)，
但是說謊者會不告知真實(shí)喜好，而且會說是另外三支球隊(duì)的支持者。
訪問所有的村民之后，得到的訪談結(jié)果如下 :
A的支持者有90，
B的支持者有100，
C的支持者有80，
D的支持者有80。
問村里有多少個說謊者。
下面是正式題 :
你有一個凸的 n 邊形，其每個頂點(diǎn)都有一個整數(shù)值。給定一個整數(shù)數(shù)組 values ，
其中 values[i] 是第 i 個頂點(diǎn)的值（即 順時針順序 ）。
假設(shè)將多邊形 剖分 為 n - 2 個三角形。
對于每個三角形，該三角形的值是頂點(diǎn)標(biāo)記的乘積，
三角剖分的分?jǐn)?shù)是進(jìn)行三角剖分后所有 n - 2 個三角形的值之和。
返回 多邊形進(jìn)行三角剖分后可以得到的最低分 。
輸入：values = [1,2,3]。
輸出：6。
解釋：多邊形已經(jīng)三角化，唯一三角形的分?jǐn)?shù)為 6。
來自左程云。
答案2023-08-26：
大體過程如下：
1.在main函數(shù)中，定義一個整數(shù)數(shù)組values表示每個頂點(diǎn)的值。
2.調(diào)用minScoreTriangulation函數(shù)，傳入values數(shù)組，并將返回的最低分?jǐn)?shù)打印出來。
3.在minScoreTriangulation函數(shù)中，首先獲取頂點(diǎn)數(shù)量N，然后創(chuàng)建一個二維切片dp作為動態(tài)規(guī)劃的緩存。
4.初始化dp切片為-1。
5.返回調(diào)用遞歸函數(shù)f，傳入values、起始位置0、結(jié)束位置N-1以及dp切片。
6.在f函數(shù)中，首先處理遞歸終止條件，如果起始位置i大于等于結(jié)束位置j-1，返回0，表示無法構(gòu)成三角形。
7.如果在緩存中存在dp[i][j]的結(jié)果，則直接返回結(jié)果。
8.初始化ans變量為math.MaxInt32，用于存儲最小的分?jǐn)?shù)。
9.對于所有的m從i+1到j(luò)-1，遍歷所有可能的分割點(diǎn)。
10.對于每個分割點(diǎn)m，計算分割兩部分的分?jǐn)?shù)和，并取最小值。
11.更新ans為當(dāng)前最小值。
12.將ans存入緩存dp[i][j]中。
13.返回ans作為結(jié)果。
總的時間復(fù)雜度為O(N^3)，因?yàn)橛腥龑忧短籽h(huán)，每層循環(huán)的次數(shù)最大為N。
總的空間復(fù)雜度為O(N^2)，因?yàn)樾枰獎?chuàng)建一個二維切片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]范圍上這些點(diǎn)，要分解成多個三角形
//?三角形一個端點(diǎn)是values[i]，另一個端點(diǎn)是values[j]
//?那么第三個點(diǎn)在i+1....j-1之間選
//?比如選了m點(diǎn)?:?i......m.......j
//?當(dāng)前獲得的分?jǐn)?shù)為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?{
????????//?不夠三個點(diǎn)，不會有得分
????????return?0;
????}
????if?dp[i][j]?!=?-1?{
????????//?緩存的答案
????????//?如果命中直接返回
????????//?看體系學(xué)習(xí)班，動態(tài)規(guī)劃的章節(jié)
????????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++完整代碼如下：
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)?{
????????//?不夠三個點(diǎn)，不會有得分
????????return?0;
????}
????if?(dp[i][j]?!=?-1)?{
????????//?緩存的答案
????????//?如果命中直接返回
????????//?看體系學(xué)習(xí)班，動態(tài)規(guī)劃的章節(jié)
????????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完整代碼如下：
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;
}
