请教一道数学题，一个整数的拆分

Question

请教个数学题
我有一个随机数，是10的整数倍，但小于等于100，即10,20,30,40,50,60,70,80,90,100
我有4个基本数，是10,20,30,40
当给出随机数的时候，将随机数，拆分成基本数的 和
问：有几种拆法

举例：随机数100，可以拆成40+40+20，也可以拆成40+40+10+10，也可以拆成40+30+20+10，怎么算出所有的拆法？

Answer 1

这道题可以使用递归的思想求解。
首先，我们将问题分成两个子问题：
对于给定的随机数，从四个基本数中选择一个数，然后求剩余数的拆分方法数。
对于给定的随机数，从四个基本数中选择两个数，然后求剩余数的拆分方法数。
为了避免重复计算，我们可以使用记忆化搜索。具体来说，我们可以建立一个二维数组 $dp$，其中 $dp[i][j]$ 表示拆分数为 $i$，从第 $j$ 个基本数开始拆分的方法数。
对于第一个子问题，我们可以写出如下的递推式：
$$ dp[i][j] = \sum_{k=0}^{i/j} dp[i-kj][j+1] $$
其中 $k$ 是第 $j$ 个基本数的个数，$i/j$ 是剩余数 $i$ 最多可以拆分的个数。
对于第二个子问题，我们可以写出如下的递推式：
$$ dp[i][j] = \sum_{k=0}^{i/j} dp[i-kj][j+1] $$
其中 $k$ 是第 $j$ 个基本数的个数，$i/j$ 是剩余数 $i$ 最多可以拆分的个数，但是要满足 $i-kj\geq j$。
最终的答案就是将这两个子问题的结果相加。
以下是用 C# 语言实现的代码：

using System;

class Program
{
    static int[,] dp = new int[101, 5];

    static int dfs(int n, int start)
    {
        if (n < 0 || start > 4)
            return 0;
        if (n == 0)
            return 1;
        if (dp[n, start] != -1)
            return dp[n, start];
        int res = 0;
        for (int i = start; i < 4; i++)
            res += dfs(n - i * 10, i + 1);
        dp[n, start] = res;
        return res;
    }

    static void Main(string[] args)
    {
        for (int i = 0; i <= 100; i++)
            for (int j = 0; j < 5; j++)
                dp[i, j] = -1;
        int ans = 0;
        for (int i = 10; i <= 100; i += 10)
            for (int j = 0; j < 4; j++)
                ans += dfs(i - j * 10, j + 1);
        Console.WriteLine(ans);
    }
}