骰子的点数
这题还挺难理解的,把剑指offer书上的代码扒下来备忘。
C++ 代码
class Solution {
public:
vector<int> numberOfDice(int n) {
if(n < 1)return {};
int g_max_value = 6;
vector<vector<int>> probabilities (2, vector<int>(g_max_value * n + 1));
for(int i = 0; i < g_max_value * n + 1; i ++ ){
probabilities[0][i] = 0;
probabilities[1][i] = 0;
}
int flag = 0;
for(int i = 1; i <= g_max_value; i ++ ){
probabilities[flag][i] = 1;
}
for(int k = 2; k <= n; k ++ ){
for(int i = 0; i < k; i ++ )probabilities[1 - flag][i] = 0;
for(int i = k; i <= g_max_value * k; i ++ ){
probabilities[1 - flag][i] = 0;
for(int j = 1; j <= i && j <= g_max_value; ++ j)
probabilities[1 - flag][i] += probabilities[flag][i - j];
}
flag = 1- flag;
}
vector<int> res;
for(auto x : probabilities[flag]){
if(x != 0)res.push_back(x);
}
return res;
}
};