阿里3.17 笔试题

第一题

n副扑克，张数为m，大小为1～m，每幅扑克抽一张，求和恰好为k的组合数，结果对10e9+7取余数。
思路：动态规划。和为i，j副扑克，，dp[i][j] = dp[i-1][j-1]+...+dp[i-m][j-1](此处需要判断 i-m>0 )。初始化，j=1，i<=m,dp[i][j] = 1; i==j,dp[i][j] = 1,后面的情况不可能存在，所以推出循环。

代码

欢迎指正。

public class Main {
static long MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int k = scanner.nextInt();
            System.out.println(solution(m, n, k));
        }
    }

    public static int solution(int m, int n, int k) {
        if (k < n || k > n * m) return 0;
        long[][] dp = new long[k + 1][n + 1];
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                    //后面的结果不可能发生
                    break;
                } else if (j == 1) {
                    if (i <= m) dp[i][j] = 1;
                } else {
                    for (int p = 1; p <= m; p++) {
                        if (i - p <= 0)
                            break;
                        dp[i][j] += dp[i - p][j - 1];
                        dp[i][j] %= MOD;
                    }
                }
            }
        }
        return (int) (dp[k][n] % MOD);
    }
}

第二题

没时间做了，题目太长了，记不清楚了。但是大概看了一下，不是特别难。