Leetcode题解剑指 Offer 60. n个骰子的点数

PROBLEM

难度中等

MY ANSWER

动态规划，res[i][j]代表用 i 个骰子掷出 j 值。时间复杂度为O(n^2)，空间复杂度O(n^2)。

递推方程为：res[i][j] = (res[i-1][j-1] + ... + res[i-1][j-6]) / 6

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<double>> res(n + 1, vector<double> (n * 6 + 1, 0));
        for(int i = 1; i <= 6; i++) {
            res[1][i] = 1.0 / 6.0;
        }
        for(int i = 2; i <= n; i++) {
            for(int j = i; j <= 6 * i; j++) {
                double ans = 0;
                for(int k = 1; k <= 6; k++) {
                    if(j - k > 0) {
                        ans += res[i-1][j-k] / 6.0;
                    }
                }
                res[i][j] = ans;
            }
        }
        vector<double> ret;
        ret.assign(res[n].begin() + n, res[n].end());
        return ret;
    }
};

BETTER SOLUTION

不需要储存全部的res，只用两个数组存储当前结果与上一行结果即可，空间复杂度降到O(n)。另外将递推改为正向：tmp[j + k] += dp[j] / 6.0;进行正向计算，省略了条件判断，同时也减少了计算次数。

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            vector<double> tmp(5 * i + 1, 0);
            for (int j = 0; j < dp.size(); j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

SUMMARY

使用动态规划来计算概率问题，也是空间换时间的一种。
动态规划只需要前一步的结果、不需要前面整个过程的结果时，就可以只存储上一步结果，不需要把整个过程存下来，从而减少空间复杂度。
有时计算可以考虑将逆向改为正向，代码更简洁甚至计算次数更少。