c++刷剑指offer（面试题60. n个骰子的点数）【动态规划】

糖逗

题目描述：面试题60. n个骰子的点数

1. 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
   
2. 
   
3.  
   
4. 
   
5. 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
   
6. 
   
7.  
   
8. 
   
9. 示例 1:
   
10. 
    
11. 输入: 1
    
12. 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
    
13. 示例 2:
    
14. 
    
15. 输入: 2
    
16. 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
    
17.  
    
18. 
    
19. 限制：
    
20. 
    
21. 1 <= n <= 11

复制代码

1. #include <vector>
   
2. #include <math.h>
   
3. #include<iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. vector<double> solution(int input){
   
8.         vector<double> result;
   
9.         int dp[input][6*input] = {0};
   
10.         for(int i = 0; i < 6; i++){
    
11.                 dp[0][i] = 1;
    
12.         }
    
13.         for(int i = 1; i < input; i++){
    
14.                 for(int j = 0; j < input * 6; j++){
    
15.                         for(int k = 1; k <= 6; k++){
    
16.                                 if(j - k < 0) break;
    
17.                                 dp[i][j] += dp[i-1][j-k];
    
18.                         }
    
19.                 }
    
20.         }
    
21.         int total = pow(6, input);
    
22.         for(int i = input - 1; i < 6*input; i++){
    
23.                 result.push_back(dp[input-1][i] * 1.0 / total);
    
24.         }
    
25.         return result;
    
26.          
    
27. }
    
28. 
    
29. int main(void){
    
30.         int input;
    
31.         cout << "send a number" << endl;
    
32.         cin >> input;
    
33.        
    
34.         vector<double> result;
    
35.         result = solution(input);
    
36.         for(int i = 0; i < result.size(); i++){
    
37.                 cout << result[i] << " ";
    
38.         }
    
39.         cout << endl;
    
40.         return 0;
    
41. }

复制代码

注意：
1.动态规划的思路
（1）确定状态
（2）确定状态转移矩阵
（3）确定边界