题目
将一个骰子投掷n次，获得的总点数为s，s的可能范围为n~6n。
掷出某一点数，可能有多种掷法，例如投掷2次，掷出3点，共有[1,2],[2,1]两种掷法。
请求出投掷n次，掷出n~6n点分别有多少种掷法。
样例1
输入：n=1
输出：[1, 1, 1, 1, 1, 1]
解释：投掷1次，可能出现的点数为1-6，共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。
样例2
输入：n=2
输出：[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
解释：投掷2次，可能出现的点数为2-12，共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。
所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。

解法：DP

数组dp[i][j]表示用i个骰子扔出和为j的可能数，因为第i个骰子可能扔出1-6的点数，则dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6]，由于我们只需要用到最后一次的结果，因此为了节省空间可以使用滚动数组，将二维dp数组变为一维
时间复杂度O(n2)，空间复杂度O(n)

  1. class Solution {
  2. public:
  3.     vector<int> numberOfDice(int n) {
  4.         vector<int> ans(6 * n + 1, 0);
  5.         for (int i = 1; i <= 6; i++)
  6.             ans[i] = 1;
  8.         for (int i = 2; i <= n; i++) {
  9.             for (int j = 6 * i; j >= i; j--) {
  10.                 ans[j] = 0;
  11.                 for (int k = 1; k <= 6; k++) {
  12.                     if (j > k) {
  13.                         ans[j] += ans[j - k];
  14.                     }
  15.                 }
  16.             }
  17.         }
  19.         return vector<int>(ans.begin() + n, ans.end());
  20.     }
  21. };