题目描述
算法1
(自下而上的DP) $O(n)$
时间复杂度
Python 代码
class Solution:
def change(self, B: int, A: List[int]) -> int:
dp = [0 for _ in range(B+1)] #dp = [0] * (amount + 1) #amount指B
dp[0] = 1
for i in A:
for j in range(i,B+1):
if i <= j:
dp[j] += dp[j-i]
return dp[-1]
C++
class Solution {
public:
int change(int amount, vector<int>& coins) {
//Edge Cases
if(amount==0) return 1;
if(coins.size()==0) return 0;
//Make a dp array
vector<int> dp(amount+1,0);
dp[0]=1;
for(int i=0;i<coins.size();i++)
{
for(int j=1;j<=amount;j++)
{
if(coins[i]<=j)
dp[j] = dp[j] + dp[j-coins[i]];
}
}
return dp[amount];
}
};
用于理解版本: Recursion
def change(self, amount, coins):
@functools.lru_cache(None)
def change_(amount, coins):
if amount == 0: return 1
if amount < 0 or len(coins) == 0: return 0
return change_(amount - coins[-1], coins) + change_(amount, coins[:-1])
return change_(amount, tuple(coins))