首页 > 阿里笔试 3.17
头像
hhxx201910142113173
编辑于 2021-04-02 16:06
+ 关注

阿里笔试 3.17 内部员工回复

阿里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);
    }
}

第二题

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

全部评论

(13) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐