剑指 Offer 60. n个骰子的点数（动态规划）

[剑指 Offer 60. n个骰子的点数]

思路：

\qquad题目其实不难，写这篇博客主要是记录下C++使用vector开多维数组。

\qquad思路类似于走台阶，每次可以走1，2，3阶，问到每一级台阶有多少种走法。这道题目是丢n次骰子，问每种骰子点数和有多少种组合。求出每种点数和的所有组合数，然后除一下总数就是概率了。状态转移方程如下：

dp[i][j]=∑k=16dp[i−1][j−k]dp[i][j]=\sum_{k=1}^6dp[i-1][j-k]dp[i][j]=k=1∑6​dp[i−1][j−k]

\qquad其中dp[i][j]dp[i][j]dp[i][j]表示第iii次投骰子的时候，点数和为jjj的组合的总数。

代码：

class Solution {public:vector<double> dicesProbability(int n) {vector<vector<int>> sum (n + 1, vector<int> (100, 0));for(int i = 1;i < 7; ++i) sum[0][i] = 1;for(int i = 1;i < n; ++i){for(int j = 0;j < 100; ++j){for(int k = 1;k < 7; ++k){if(j >= k) sum[i][j] += sum[i - 1][j - k];}}}int tol = 0;for(int i = 0;i < 100; ++i){if(sum[n - 1][i] > 0) tol += sum[n - 1][i];}vector<double> ans;for(int i = 0;i < 100; ++i){if(sum[n - 1][i] > 0) ans.push_back(sum[n - 1][i] * 1.0 / tol);}return ans;}};