剑指offer2之n个骰子点数之和

题目(n 个骰子点数之和)

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

算法思路

首先，剑指offer上的本题题解过于晦涩，作者未明确指出其实这道题是一题dp(动态规划)题。
首先，扔 n 个骰子的解可以由扔 n-1 骰子的解推出，即原问题包含了子问题的解(状态转移)；其次，对于如果使用递归的话，那么必定存在重复的子问题；因此，本题适用于动态规划的解法。
那么，首先构造状态转移方程：设扔 n 个骰子时排列数之和为 s 的函数为f(n,s)，那么如果先扔了 n-1 个骰子，则扔最后一个骰子就有 6 种情况(最后一个投出1、2、3、4、5、6)来得到排列数之和 s(前面的 6 种状态(解)可以推出当前状态(解))。即，f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6),n<=s<=6n。而当 s6n，则f(n,s)=0。初始状态位 n=1，f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

算法实现(递归版)

递归版的实现只需要对 N 个骰子遍历每种可能的排列数即可。(自顶向上递归下去，自底向上回溯到顶得解)

算法实现(循环版)

循环版首先需要遍历每个骰子的情况，然后针对每个骰子的，再遍历其可能的排列数范围。(自底向上求出所有解)

参考

[1] <<剑指offer2>>