题目

题解

这道题有两个方法，递归与动态规划，动态规划会超时。而且我刚开始看递归反而看不懂，因此转为先看动态规划，借助路漫漫我不畏的题解加图解，理解了动态规划的思想，进而明白了递归的思想

1. 动态规划

重点看上面大佬提供的图解

  • 时间复杂度$O(n^{2})$，（不确定，感觉是两个n的循环套一个6的循环）
  • 空间复杂度$O(n)$，dp数组
class Solution {//一个方法。1.一维dp
public:
    vector<double> twoSum(int n) {
        vector<int> dp(70, 0);//n<=11，动态规划最大用66个数组这里用70个
        //先初始化dp[1]，即只有一个骰子的情况，此时前6个数为1
        for(int i = 0; i <= 6; ++i){
            dp[i] = 1;
        }
        //进行动态规划，从2个骰子到n个骰子，注意判别条件是小于等于
        for(int i = 2; i <= n; ++i){
            //从后向前挨个更新dp数组
            //从6*i开始，一直更新到第i个数，这个就是投掷i个骰子的数字取值范围
            for(int j = 6 * i; j >= i; --j){
                //重点1！！！注意要先把该更新的位置设置为0再进行后面的累加，否则会累加上dp[i-1]的数据，出错
                dp[j] = 0;
                //累加当前这个数的前6个数的dp，这里可以这么理解
                //即投第i个骰子有1~6 6种情况，而要累加到当前值，就要借助dp[i-1]~dp[i-6]的值
                for(int cur = 1; cur <= 6; ++cur){
                    //重点2！！！注意累加值会小于i-1，因为i-1个骰子最小值就是i-1
                    //累加之前的数据其实是上一个dp的值
                    if(j - cur < i - 1) break;
                    //累加上述的前6个值
                    dp[j] += dp[j-cur];
                }
            }
        }
        vector<double> res;
        //当前存的都是可能出现的情况次数，还要转化为概率
        int all = pow(6, n);//所有可能出现的情况的个数
        //将最后一个dp的情况出现次数转化为概率
        //注意范围是n~6*n
        for(int i = n; i <= 6 * n; ++i){
            //这里注意要除以一个1.0将int转化为double
            res.push_back(dp[i] * 1.0 / all);
        }
        return res;
    }
};

2. 递归

  • 时间复杂度$O(6^{n})$，必超时
  • 空间复杂度$O(1)$

这个方法必超时，但是我们可以借助这个问题思考一下dp和递归的关系。个人感觉对这道题来说

  1. 动态规划就是一种带记忆的递归思想
  2. 动态规划自顶向下，递归自底向上再返回

其实还借助大佬提供的图解，即动态规划每次存下来当前的状态，下一次状态时直接从数组中取值即刻，空间占用多少取决于和前几次的状态有关。
而递归就是每次取前面状态时需要再重新从下到上算一下，推算到只有一个骰子的情况，这样造成了大量的重复计算，因此会超时。