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

糖逗

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

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

 

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

 

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
 

限制：

1 <= n <= 11

#include <vector>
#include <math.h>
#include<iostream>

using namespace std;

vector<double> solution(int input){
        vector<double> result;
        int dp[input][6*input] = {0};
        for(int i = 0; i < 6; i++){
                dp[0][i] = 1;
        }
        for(int i = 1; i < input; i++){
                for(int j = 0; j < input * 6; j++){
                        for(int k = 1; k <= 6; k++){
                                if(j - k < 0) break;
                                dp[i][j] += dp[i-1][j-k];
                        }
                }
        }
        int total = pow(6, input);
        for(int i = input - 1; i < 6*input; i++){
                result.push_back(dp[input-1][i] * 1.0 / total);
        }
        return result;
         
}

int main(void){
        int input;
        cout << "send a number" << endl;
        cin >> input;
        
        vector<double> result;
        result = solution(input);
        for(int i = 0; i < result.size(); i++){
                cout << result[i] << " ";
        }
        cout << endl;
        return 0;
}

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