2023阿里灵犀互娱春招算法题

前言

原文地址：https://xuedongyun.cn/post/50833/

怪物砍法

题目

题目已经找不到了，只能口述。怪物有n滴血，你有k个技能，每个技能能打1, 2, 3, 4, …, k滴落血。假设每个技能都能用无限次，每个回合用一次技能，不限回合数。问恰好能把怪物打死的打法。

输入描述

输入两个正整数n和k，代表怪物的血量和技能的数量
1 <= n <= 1000
1 <= k <= 100

输出描述

一个整数，代表打法的数量对10^9+7取模的值。

样例输入

3 2

样例输出

3

解法

刚开始做这道题，一直在想打法可能会重复，该如何解决重复的问题。后面想到一种二维dp的方法。假设dp(i, j)表示怪物i滴血，j次打死的打法数量，那么有状态转移方程：

因为最后一次伤害不同，所以一定不会出现重复的情况。打死一只n滴血的怪物需要的回合数最少为：，最大为：。我们只需要将回合数在这个区间的打法求和即可。

代码实现

long MOD = 1_000_000_007;

k = k > n ? n : k;
int minSkillNum = (int) Math.ceil(n / k);
int maxSkillNum = n;

// i滴血，j刀砍死
long[][] dp = new long[n + 1][maxSkillNum + 1];
// 1刀砍死
for (int i = 1; i <= k; i++) {
    dp[i][1] = 1;
}
// 血只有1滴
dp[1][1] = 1;

for (int i = 2; i <= n; i++) {
    for (int j = Math.max((int) Math.ceil(i / k), 2); j <= i; j++) {
        for (int l = 1; l <= Math.min(k, i-1); l++) {
            dp[i][j] += dp[i - l][j - 1];
            dp[i][j] = dp[i][j] % MOD;
        }
    }
}

long total = 0;
for (int i = minSkillNum; i <= maxSkillNum; i++) {
    total += dp[n][i];
    total = total % MOD;
}

System.out.println(total)

算法复杂度：

更优解法

之前想复杂了，假设dp[i]表示i滴血的打法，那么有状态转移方程：

我们只看最后一击即可，因此绝不会重复

代码实现

一定要考虑怪物0滴血的情况。比如怪物4滴血时，可以用伤害为4的技能一刀打死，此时就会出现加dp[0]的情况

int n = 1000;
int k = 100;

long MOD = 1_000_000_007;

k = k > n ? n : k;

long[] dp = new long[n+1];
// 怪物0滴血，只有一种砍法
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
        if (i - j < 0) {
            break;
        }
        dp[i] += dp[i - j];
        dp[i] = dp[i] % MOD;
    }
}
System.out.println(dp[n]);

算法复杂度：

冬云的博客

2023阿里灵犀互娱春招算法题

前言

怪物砍法

题目

解法

代码实现

更优解法

代码实现