AcWing80 骰子的点数(线性dp)

#define pb push_back
class Solution {
public:
    vector<int> numberOfDice(int n) {
      int f[15][100];  // 投i次，总和为j的投掷可能
      memset(f, 0, sizeof(f));
      for (int i = 1; i <= 6; i++) f[1][i] = 1;
      for (int i = 1; i <= n; i++) { // 枚举第几次投掷
        for (int j = 1; j <= i*6; j++) { // 枚举投掷的结果
          for (int k = 1; k <= 6; k++) { // 枚举当前这次是从哪里转移过来的
            if (j > k) {
              f[i][j] += f[i-1][j-k];
            }
          }
        }
      }
      vector<int> res;
      for (int i = n; i <= n*6; i++) res.pb(f[n][i]);
      return res;
    }
};

原文地址：http://www.cnblogs.com/chelly-algorithm/p/16814965.html