剑指offer- n个骰子的点数
2020-04-21 本文已影响0人
棉花糖7
这道题简直不敢相信是“简单”的题目，我看了四五个小时，到现在还懵懵的，不知道怎么回事，只能把代码敲一遍，看之后能不能理解了。
方法一：二维动态规划，dp[i][j] 表示 掷完i枚骰之后，点数j可能出现的次数
方法二：一维动态规划，dp[j]表示，掷完n枚骰之后，点数j可能出现的次数
题目
code
其中“一维动态规划”中，对 if (j-cur< i-1){ break;} 的解释：
i表示阶段，也就是扔了几个骰子；j表示 i 这个阶段可能出现的总点数，cur 是第 i 颗骰子的点数，所以 j = cur + 前 i - 1 个骰子可能出现的点数；因为前 i-1颗骰子可能出现的最小点数为 i - 1 ，也就是每颗骰子的点数都为 1。所以j - cur < i - 1 的所有情况是不合理的，也就是不可能出现的，因此就无需继续判断。
解题思路
