golang 解法, 执行用时: 52 ms, 内存消耗: 15.4 MB, 提交时间: 2023-10-21 23:14:32

func waysToDistribute(n int, k int) int {
    dp := make([][]int, n + 1)
    for i := range dp {
        dp[i] = make([]int, k + 1)
        if i > 0 {
            dp[i][1] = 1
        }
    }

    for j := 1; j <= k; j ++ {
        dp[j][j] = 1
    }

    mod := 1_000_000_007

    for i := 1; i <= n; i ++ {
        for j := 1; j <= k; j ++ {
            if i > j {
                dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1]
                dp[i][j] %= mod
            }
        }
    }
    return dp[n][k]
}

golang 解法, 执行用时: 68 ms, 内存消耗: 2.9 MB, 提交时间: 2023-10-21 23:14:11

const mod = 1e9 + 7

func waysToDistribute(n int, k int) int {
	dp := make([]int, n+1)
	dp1 := make([]int, n+1)
	for j := 1; j <= k; j++ {
		dp1[j] = 1
		for i := j + 1; i <= n; i++ {
			dp1[i] = (dp1[i-1]*j + dp[i-1]) % mod
		}
		dp,dp1 = dp1,dp
	}
	return dp[n]
}

java 解法, 执行用时: 106 ms, 内存消耗: 54.8 MB, 提交时间: 2023-10-21 23:13:42

class Solution {
    public int waysToDistribute(int n, int k) {
        long[][] res = new long[n][k];
        // 袋子数大于糖块数的情况不作处理，默认为0
        // 只有一个袋子
        for (int i = 0; i < n; i++) {
            res[i][0] = 1;
        }
        // 袋子数小于等于糖块数, j为袋子数-1, i为糖块数-1
        for (int j = 1; j < k; j++) {
            for (int i = j; i < n; i++) {
                res[i][j] = (res[i - 1][j] * (j + 1) + res[i - 1][j - 1]) % 1000000007;
            }
        }
        return (int)res[n - 1][k - 1];
    }
}

python3 解法, 执行用时: 3756 ms, 内存消耗: 38.4 MB, 提交时间: 2023-10-21 23:13:27

class Solution:
    def waysToDistribute(self, n: int, k: int) -> int:
        MOD = 10 ** 9 + 7

        dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
        for i in range(1, k + 1):
            dp[i][i] = 1        #每个袋子放一个

        for i in range(1, k + 1):       #袋子
            for j in range(i + 1, n + 1):   #糖果数
                #新的糖果，单独一个盒子
                dp[i][j] = dp[i-1][j-1]
                #新的糖果，加入其他的盒子
                dp[i][j] += dp[i][j-1] * i

                dp[i][j] %= MOD
        
        return dp[k][n]
        
        
    def waysToDistribute2(self, n: int, k: int) -> int:
        dp=[[0]*(n+1) for _ in range(k+1)]
        for i in range(1,k+1):
            dp[i][i]=1
            for j in range(i+1,n+1):
                dp[i][j]=(dp[i][j-1]*i+dp[i-1][j-1])%(10**9+7)
        return dp[-1][-1]

cpp 解法, 执行用时: 72 ms, 内存消耗: 10 MB, 提交时间: 2023-10-21 23:12:58

class Solution {
public:
    int waysToDistribute(int n, int k) {
        int MOD = 1e9 + 7;

        int dp[k+1][n+1];    memset(dp, 0, sizeof(dp));
        for (int i = 1; i < k + 1; i ++)
            dp[i][i] = 1;
        
        for (int i = 1; i < k + 1; i ++) {    //袋子数
            for (int j = i + 1; j < n + 1; j ++) {    //糖果数
                //----新加的糖果，单独一个袋子
                dp[i][j] = dp[i-1][j-1] % MOD;
                //----新加的糖果，加入一个有糖果的袋子
                dp[i][j] = (dp[i][j] + (long long)dp[i][j-1] * i) % MOD;
            }
        }

        return dp[k][n];
    }
};

cpp 解法, 执行用时: 96 ms, 内存消耗: 10.7 MB, 提交时间: 2023-10-21 23:12:19

using LL = long long;
const int MOD = 1e9 + 7;
class Solution {
public:
    int dp[1005][1005];
    int waysToDistribute(int n, int k) {
        if(n == k) return 1;
        for(int i = 0;i <= n;i ++) dp[i][0] = 1;
        for(int i = 1;i <= k;i ++) {
            dp[i][i] = 1;
            for(int j = i + 1;j <= n;j ++) {
                dp[i][j] = ((LL)dp[i][j - 1] * i + dp[i - 1][j - 1]) % MOD;
            }
        }
        return dp[k][n];
    }
};