掷骰子结果之和等于特定数的方法从递归到结束

algorithm

---

掷骰子结果之和等于特定数的方法

• 掷骰子结果之和等于特定数的方法，题目大意，给定$d$个骰子，每个骰子$f$面，分别是$1,2,\cdots f$，给定一个数$target$。试问有多少种方法可以获取到掷骰子 d 次，每次的骰子面数字之和等于$target$。例如：$d = 1, f = 6, target = 3$ 那么，$f(d,f,target)=1$，因为一个骰子，掷的结果等于 3 的方式只有一种。再如：$d = 2, f = 6, target = 7$，$S(d,f,target) = 6$，这 6 种情况分别是：$1+6, 2+5, 3+4, 4+3, 5+2, 6+1.$
• 理解这个题目之后，可以看出来这个题的本质是背包问题。这里每次获取的掷骰子有 f 种结果，分别装入背包中，再看剩下的如何进行掷骰子。

方法一：递归

• 直观想法，对于$S(d,f,target)$的结果，我们遍历掷一次的结果$target-1,target-2 \cdots target-f$，分别计算出小规模的情况下，结果值和等于$target-i$的方法，然后计数。

$$S(d,f,target) = \sum_{i=1}^{f}S(d-1,f,target-i)$$

• 基本的情况有如下几种：
• 1.1 $d<0 || target < 0$，认为方法数为 0
• 1.2 $d=0 \And target = 0$ 认为是一次有效的掷骰子路径。返回 1。

    const static int M = (int)(7 + 1e9);
    int numRollsToTarget(int d, int f, int target)
    {
        return targetSum(d, f, target);
    }
    int targetSum(int d, int f, int target)
    {
        if (d < 0 || target < 0)
            return 0;
        // base case,one way to roll dice
        if (target == 0 && d == 0)
            return 1;
        int c = 0;
        for (int i = 1; i <= f; i++)
        {
            if (target == i && d == 1)
            {
                c += 1;
                c %= M;
            } else if (target > i)
            {
                int x = targetSum(d - 1, f, target - i);
                x %= M;
                c += x;
                c %= M;
            }
            else
                break;
        }
        return c % M;
    }

• 时间复杂度:$T(n) = \sum^{f}_{1}{T(i)})=O(x^n)$，待确定(TODO)
• 空间复杂度:$S(n) = O(n)$。

方法二：转化为备忘录递归

• 上述方式存在子问题重复计算的情况，例如计算$S(3,4,9)$,需要计算$S(2,4,8) \cdots S(2,4,7) \cdots S(2,4,6)...$，,计算$S(2,4,8)$的时候，还需要计算$S(2,4,7)$,可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
• 对于已经计算出来的投掷结果用map来保存，例如map["1->4"]，表示$s(1,f,4)$的投掷结果。

    const static int M = (int)(7 + 1e9);
    unordered_map<string, int> umap;
    int numRollsToTarget(int d, int f, int target)
    {
        return targetSum(d, f, target);
    }
    int targetSum(int d, int f, int target)
    {
        // 非法case
        if (d < 0 || target < 0)
            return 0;
        // base case
        if (target == 0 && d == 0)
            return 1;
        string k = to_string(d) + "-" + to_string(target);
        if (umap.find(k) != umap.end()) // 已经有结果的数据直接返回
            return umap[k];
        int c = 0;
        for (int i = 1; i <= f; i++)
        {
            if (target == i && d == 1) // 一种合法情况
            {
                c += 1;
                c %= M;
            }else if (target > i) // 需要继续递归调用
            {
                int x = targetSum(d - 1, f, target - i);
                x %= M;
                c += x;
                c %= M;
            }
            else // 非法情况，target < i 说明无法继续掷骰子，来达到目标值
                break;
        }
        umap[k] = c % M;// 备忘录保存已经计算的结果
        return umap[k];
    }

• 时间复杂度：$T(n,f) = O(fn)$。
• 空间复杂度：$O(dn)$，需要使用哈希表。
• 能够通过，可优化。

方法三：掷骰子结果之和等于特定数的方法（转化为迭代计算）

• 假设$f[i,j]$ 表示$i$个骰子，掷得和为$j$的方法数。

$$f[i,j] = \sum_{k=1}^{f}f[i-1,j-k], j-k \le (i-1)*f$$

• 基础情况：$f[1,1\cdots f] = 1,f[i,i] = 1$

const static int M = (int)(7 + 1e9);
int numRollsToTarget(int d, int f, int target)
    {
        if (target > d * f)
            return 0;
        if (target == d * f)
            return 1;
        vector<vector<int>> dp;
        dp.push_back(vector<int>(f + 1, 0));
        for (int i = 1; i <= d; i++)
        {
            vector<int> r(i * f + 1, 0);
            dp.push_back(r);
        }
        for (int i = 1; i <= f; i++)
            dp[1][i] = 1;
        for (int i = 2; i <= d; i++)
        {
            dp[i][i] = 1;
            int total = i * f;
            for (int j = i + 1; j <= total; j++)
            {
                dp[i][j] = 0;
                for (int k = f; k >= 1; k--)
                {
                    int x = j - k;
                    if (x > 0 && x < dp[i - 1].size())
                    {
                        dp[i][j] += dp[i - 1][j - k] % M;
                        dp[i][j] %= M;
                    }
                }
                if (j == target)
                    break;
            }
        }
        return dp[d][target];
        // return targetSum(d, f, target);
    }

• 时间复杂度:$O(d*f*target)$,空间复杂度：$O(target^2)$
• 这里的空间方面可以优化，计算$f[i,j]$时，只用到了$f[i-1,k]$的内容。