一.题目描述
把n个骰子仍在地上，所有的骰子朝上的一面的点数之和为s，输入n，打印出s所有可能的值出现的概率。
二.题解
《剑指offer》上给出的两种方法，尤其是代码，晦涩难懂且没有注释。而n个骰子的问题实质就是一个动态规划问题，所以文本主要从动态规划的角度来求解这个问题。首先该问题具备DP的两个特征：最优子结构性质和子问题的重叠性。具体的表现在：(1)n个骰子的点数依赖于n-1个骰子的点数，相当于在n-1个骰子点数的基础上再进行投掷。(2)求父问题的同时，需要多次利用子问题。由此定义状态转移方程为$f(n,k)$表示$n$个骰子点数和为$k$时出现的次数，于是可得:
$$ f(n,k) = f(n- 1, k- 1) + f(n- 1, k- 2) + f(n- 1, k- 3) + f(n- 1, k- 4) + f(n- 1, k- 5) + f(n- 1, k- 6) $$
其中 $n > 0$且$k <= 6n$。其中$f(n-1,k-i)$表示的是第n次掷骰子时，骰子的点数为$i$对应的情况，所以从$k-1$到$k-6$分别对应第n次掷骰子时骰子正面为$1$到$6$的情况。而初始状态可以定义为：
$$ f(1,1) = f(1,2) = f(1,3) = f(1,4) = f(1,5) = f(1,6) = 1 $$
所以根据这两个方程，给出的实现代码如下：
#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<set>
#include<map>
#include<stack>
#define MAX_NUM 100
using namespace std; void FindSum(int n)
{
if(n <= 0)
return;
int sum = 0;
int arr[n + 1][6 * n + 1];
memset(arr,0,sizeof(arr));
for(int i = 1; i <= 6; i++)//初始状态
arr[1][i] = 1;
for(int i = 2; i <= n; i++)//状态转移方程
{
for(int j = i; j <= 6*i; j++)//注意j的范围受i影响
{
arr[i][j] += (arr[i - 1][j - 1] + arr[i - 1][j - 2] + arr[i - 1][j - 3] + arr[i - 1][j - 4] + arr[i - 1][j - 5]
+arr[i - 1][j - 6]);
}
}
//输出结果
for(int i = n; i <= 6 * n; i++)
{
//cout<<"骰子的和为 "<<i<<" 时，对应的次数为："<<arr[n][i]<<endl;
sum += arr[n][i];
}
cout<<n<<"个骰子总共的次数为 "<<sum<<endl;
for(int i = n; i <= 6 * n; i++)
{
cout<<"骰子的和为 "<<i<<" 时，对应的频率为："<<(arr[n][i] * 1.0 / sum)<<endl;
} }
int main()
{
int n;
cout<<"请输入骰子的个数:"<<endl;
cin>>n;
FindSum(n);
}
此处的代码只是朴素dp的实现，用动态规划来解释，感觉比书上好理解多了....