问答

当前位置

Coin Change II 时间复杂度

  • by zz
  • 1
  • 1 年,6 月前
  • Ta: 江子特

https://www.jiuzhang.com/solution/coin-change-ii/

下面是我递归的做法,感觉是对的,但是一个很大的test case没有过,因为超时。

public int change(int amount, int[] coins) {
    return helper(amount, coins, 0);
}

public int helper(int amount, int[] coins, int lastCoin) {
    if (amount < 0) {
        return 0;
    }
    if (amount == 0) {
        return 1;
    }
    int comb = 0;
    for (int coin : coins) {
        if (coin >= lastCoin) {
            comb += helper(amount - coin, coins, coin);
        }
    }
    return comb;
}

问题:
1. 九章答案中的worst时间复杂度大概是O(硬币个数*(Amount/面值最小硬币))吗?
2. 我的递归做法为什么超时,时间复杂度是多少呢?我感觉跟答案中的时间复杂度一样哇。
谢谢!

1 个回复

2018-04-22 白助教

九章的题解复杂度是O(n*M) M是总金额。做法跟0-1背包有点像

你的递归有大量的重复计算,使用记忆化的方式更好。用一个数组记录组成每个值的种类,然后避免重复计算这个。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1