题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 举例：
输入: 1 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667] 输入: 2 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889, 0.11111,0.08333,0.05556,0.02778]我们把值设为k，k的概率： P=k 出现的次数 / 总次数； 总次数显然是6的n次方，当然里面包括很多重复的组合。
仔细分析下发现很头大，但是我们可以get到这是一道数学题！ 那我们是不是就应该想到动态规划！
动态规划解决问题的步骤是什么呢？
找出状态-——再分析状态转移方程————处理一下边界
状态；
我们从问题的最后一步入手对吧，比如倒数第二步怎么到达最后一步的，比如这个题目，最后一步是什么？ 当然是投掷n个筛子后每个k出现的次数； 那么从n-1个筛子到全投掷完，点数怎么到达k的呢？ 显然是六种情况： k-1; k-2; k-3; k-4; k-5; k-6 那么状态是不是确定出来了 dp[i][j]
i代表投掷i枚筛子；
j代表投掷i枚筛子 点数和为j**
dp[i][j]代表出现的次数
数学公式
边界： 第一次，可能的点数是i:1~6； 次数都是1 所以dp[1][i]=1;
for(int i=1;i<=6;i++) { dp[1][i]=1 }另外设想下： 投掷了n次筛子， j 的值是是n~6*n dp[i][j]的次数怎么从上一步来的我们之前列出了公式。 例如 dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
整体代码：
#include<iostream> #include<vector> using namespace std; vector<double> twoSum(int n) { vector<vector<double>>dp(n+1, vector<double>(6 * n + 1, 0)); vector<double> res; for (int i = 1;i <= 6;i++) { dp[1][i] = 1; } for (int i = 2;i <= n;i++) { for (int j = i;j <= n * 6;j++) { for (int k = 1;k <= 6;k++) { if (j <= k) break; dp[i][j] += dp[i - 1][j - k]; } } } for (int i = n;i <= 6 * n;i++) { res.push_back(dp[n][i] * 1.0 / pow(6, n)); } return res; } int main() { vector<double>res=twoSum(2); double a = 0.0; cout << "计算结果：" << endl; for (auto x : res) { cout << x << " "; a += x; } cout << endl; cout <<"看一下是不是1:"<< a; return 0; }下面这种更省空间
class Solution { public: vector<double> twoSum(int n) { vector<double>dp(6*n+1,0); vector<double> res; for(int i=1;i<=6;i++) { dp[i]=1; } for(int i=2;i<=n;i++) { for(int j=6*n;j>=i;j--) { dp[j]=0; for(int k=1;k<=6;k++) { if(j - k >= i - 1) dp[j] += dp[j - k]; } } } for(int i=n;i<=6*n;i++) { res.push_back(dp[i]*1.0/pow(6,n)); } return res; } };