前提:Dota2 游戏中,英雄沉默术士在击杀一名敌方英雄后可以获得智力
假设沉默术士每次击杀可以随机获得 2 点或 4 点额外智力,当他的额外智力为 68 时,可能的击杀敌方英雄的情况有多少种?
下面是我用动态规划实现的一种解法(不知道对不对)
public class Silencer {
private int intNum;
private int[] array;
private Silencer(int intNum) {
this.intNum = intNum;
}
private int possibleKillNumbers() {
this.array = new int[this.intNum+1];
this.array[0] = 1;
this.array[2] = 1;
if (this.intNum <= 2) {
return this.array[this.intNum];
}
for (int i = 4; i <= this.intNum; i+=2) {
this.array[i] = this.array[i-2] + this.array[i-4];
}
return this.array[this.intNum];
}
public static void main(String[] args) {
Silencer sil = new Silencer(68);
System.out.println(sil.possibleKillNumbers()); // output: 9227465
}
}
1
lihongming 2019-10-22 01:41:39 +08:00 via iPhone
不玩 dota,这道题是不是可以理解为 2 和 4 有多少种可能组成 68 ?
|
2
geelaw 2019-10-22 01:48:18 +08:00 via iPhone
这个数列很简单,你要算的是 Fibonacci[33]
|
3
Xs0ul 2019-10-22 02:00:18 +08:00
从你字面意思来说不太对, possibleKillNumbers 看起来是不包含顺序的
从你的代码来说,你要求的实际就是第 N / 2 个斐波那契数 |
4
paouke 2019-10-22 09:11:31 +08:00 via iPhone
可以理解为 68 级台阶,青蛙每次上 2 级或者 4 级,有多少种上法吗,哈哈
|
5
a7217107 2019-10-22 09:25:59 +08:00
递归,这就是斐波那契数列
|
6
braveheart7854 2019-10-22 10:03:37 +08:00
2x+4y=68,然后 for x=0; x<=68/2; x++,求 y
|
8
barnetime 2019-10-22 20:28:14 +08:00
```
def possibleKillNum(target: Int) : Int = { val k1 = 2 val k2 = 4 if (target == 2) return 1 if (target == 4) return 2 possibleKillNum(target - k1) + possibleKillNum(target - k2) } ``` |
9
barnetime 2019-10-22 21:01:55 +08:00
```
//从上面的递归 到加上缓存(也叫记忆化) 递推 def possibleKillNum1(target: Int, cash : mutable.Map[Int, Int]) : Int = { //需要传一个空 Map 做缓存 if (cash.isEmpty) { cash += 2 -> 1 cash += 4 -> 2 } val k1 = 2 val k2 = 4 if (cash.getOrElse(target, null) == null) { val r = possibleKillNum1(target - k1, cash) + possibleKillNum1(target - k2, cash) cash += target -> r r } else { cash(target) } } ``` |
10
promontory123 2019-10-23 11:06:52 +08:00
2n 阶台阶,单次 2 或 4 阶,最多跳跃多少次 减去 最少跳跃多少 次加一
|
11
dezhou 2019-10-25 08:51:12 +08:00 via Android
( x+x^2 )^34 的 x^68 的系数
|
12
RicardoY 2019-11-02 21:34:30 +08:00 via Android
这个稍微简单点了..我记得有用拍拍熊打野和小鱼刮痧作为背景的题目..就比较难了
|