中兴算法：击杀怪物的最少技能数，回溯

def get_skill_num(As, xs, n, m):
    if n<=0&nbs***bsp;m<=0:
        return 0
    temp = [False]*n  # temp[i]表示技能未使用
    res = []          # 每个使用过技能造成的伤害
    results = []      # 击杀成功的可能技能数

    # m表示剩余血量
    def get_res(m):
        # print(res, m)
        if m<=0:        # 当血量<=0，击杀成功， 追加技能数到结果中
            results.append(len(res))
            return
        if False not in temp:      # 技能用完，但未击杀，返回
            return
        for i in range(n):         # 遍历每个未使用的技能
            if temp[i]==False:
                temp[i] = True            # 设置技能已使用
                if m<=xs[i]:              # 若剩余点数少于该技能阈值
                    res.append(2*As[i])   # 双倍伤害
                    m -= 2*As[i]          # 剩余血量减少
                    get_res(m)            # 递归使用其他技能
                    m += 2 * As[i]        # 回溯，不使用该技能
                else:
                    res.append(As[i])
                    m -= As[i]
                    get_res(m)
                    m += As[i]
                temp[i] = False           # 回溯， 不使用该技能
                res.pop()                 # 回溯，不使用该技能
    get_res(m)
    if results==[]:  # 如果各种技能顺序组合都不能击杀，该list是空的
        return -1
    res = results[0]   # 返回最小击杀技能数
    for i in results:
        res = min(i, res)
    return res

if __name__ == "__main__":
    n, m = 3, 100    # n，技能数；m，怪物血量
    As = [10, 45, 5]     # 每个技能的伤害
    xs = [20, 84, 40]    # 触发每个技能暴击的条件——怪物的剩余血量
    res = get_skill_num(As, xs, n, m)
    print(res)

    xs1 = [20, 89, 40]  # 触发每个技能暴击的条件——怪物的剩余血量
    res = get_skill_num(As, xs1, n, m)
    print(res)

    xs2 = [20, 90, 40]  # 触发每个技能暴击的条件——怪物的剩余血量
    res = get_skill_num(As, xs2, n, m)
    print(res)