无聊想到个算法题

[qiuhanyuan]

前提：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
    }
}

[lihongming]

不玩 dota，这道题是不是可以理解为 2 和 4 有多少种可能组成 68 ？

[geelaw]

这个数列很简单，你要算的是 Fibonacci[33]

[Xs0ul]

从你字面意思来说不太对, possibleKillNumbers 看起来是不包含顺序的

从你的代码来说,你要求的实际就是第 N / 2 个斐波那契数

[paouke]

可以理解为 68 级台阶，青蛙每次上 2 级或者 4 级，有多少种上法吗，哈哈

[a7217107]

递归，这就是斐波那契数列

[braveheart7854]

2x+4y=68,然后 for x=0; x<=68/2; x++，求 y

[Dogergo]

@paouke 昨天面试问这个问题，n 阶台阶，单次 2 或 4 阶，有多少种上法，现在还在懵比

[barnetime]

```

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)
}



```

[barnetime]

```
//从上面的递归 到加上缓存(也叫记忆化) 递推

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)
}
}



```

[promontory123]

2n 阶台阶，单次 2 或 4 阶，最多跳跃多少次 减去 最少跳跃多少 次加一

[dezhou]

（ x+x^2 ）^34 的 x^68 的系数

[RicardoY]

这个稍微简单点了..我记得有用拍拍熊打野和小鱼刮痧作为背景的题目..就比较难了