File tree Expand file tree Collapse file tree 5 files changed +97
-9
lines changed
solution/0500-0599/0518.Coin Change 2 Expand file tree Collapse file tree 5 files changed +97
-9
lines changed Original file line number Diff line number Diff line change 3333
3434<p><strong>示例 3:</strong></p>
3535
36- <pre><strong>输入:</strong> amount = 10, coins = [10]
36+ <pre><strong>输入:</strong> amount = 10, coins = [10]
3737<strong>输出:</strong> 1
3838</pre>
3939
5555
5656<!-- 这里可写通用的实现逻辑 -->
5757
58+ 完全背包问题
59+
5860<!-- tabs:start -->
5961
6062### **Python3**
6163
6264<!-- 这里可写当前语言的特殊实现逻辑 -->
6365
6466```python
65-
67+ class Solution:
68+ def change(self, amount: int, coins: List[int]) -> int:
69+ dp = [0 for i in range(amount + 1)]
70+ dp[0] = 1
71+ for coin in coins:
72+ for j in range(coin, amount + 1):
73+ dp[j] += dp[j - coin]
74+ return dp[amount]
6675```
6776
6877### **Java**
6978
7079<!-- 这里可写当前语言的特殊实现逻辑 -->
7180
7281```java
82+ class Solution {
83+ public int change(int amount, int[] coins) {
84+ int[] dp = new int[amount + 1];
85+ dp[0] = 1;
86+ for (int coin : coins) {
87+ for (int j = coin; j <= amount; j++) {
88+ dp[j] += dp[j - coin];
89+ }
90+ }
91+ return dp[amount];
92+ }
93+ }
94+ ```
7395
96+ ### **Go**
97+
98+ ```go
99+ func change(amount int, coins []int) int {
100+ dp := make([]int, amount+1)
101+ dp[0] = 1
102+ for _, coin := range coins {
103+ for j := coin; j <= amount; j++ {
104+ dp[j] += dp[j-coin]
105+ }
106+ }
107+ return dp[amount]
108+ }
74109```
75110
76111### **...**
Original file line number Diff line number Diff line change 6464
6565<pre>
6666
67- <b>Input:</b> amount = 10, coins = [10]
67+ <b>Input:</b> amount = 10, coins = [10]
6868
6969<b>Output:</b> 1
7070
9595
9696## Solutions
9797
98+ Complete knapsack problem
99+
98100<!-- tabs:start -->
99101
100102### **Python3**
101103
102104```python
103-
105+ class Solution:
106+ def change(self, amount: int, coins: List[int]) -> int:
107+ dp = [0 for i in range(amount + 1)]
108+ dp[0] = 1
109+ for coin in coins:
110+ for j in range(coin, amount + 1):
111+ dp[j] += dp[j - coin]
112+ return dp[amount]
104113```
105114
106115### **Java**
107116
108117```java
118+ class Solution {
119+ public int change(int amount, int[] coins) {
120+ int[] dp = new int[amount + 1];
121+ dp[0] = 1;
122+ for (int coin : coins) {
123+ for (int j = coin; j <= amount; j++) {
124+ dp[j] += dp[j - coin];
125+ }
126+ }
127+ return dp[amount];
128+ }
129+ }
130+ ```
109131
132+ ### **Go**
133+
134+ ```go
135+ func change(amount int, coins []int) int {
136+ dp := make([]int, amount+1)
137+ dp[0] = 1
138+ for _, coin := range coins {
139+ for j := coin; j <= amount; j++ {
140+ dp[j] += dp[j-coin]
141+ }
142+ }
143+ return dp[amount]
144+ }
110145```
111146
112147### **...**
Original file line number Diff line number Diff line change 1+ func change(amount int, coins []int) int {
2+ dp := make([]int, amount+1)
3+ dp[0] = 1
4+ for _, coin := range coins {
5+ for j := coin; j <= amount; j++ {
6+ dp[j] += dp[j-coin]
7+ }
8+ }
9+ return dp[amount]
10+ }
Original file line number Diff line number Diff line change 11class Solution {
22 public int change(int amount, int[] coins) {
3- int[] f = new int[amount + 1];
4- f [0] = 1;
3+ int[] dp = new int[amount + 1];
4+ dp [0] = 1;
55 for (int coin : coins) {
6- for (int i = coin; i <= amount; ++i ) {
7- f[i ] += f[i - coin];
6+ for (int j = coin; j <= amount; j++ ) {
7+ dp[j ] += dp[j - coin];
88 }
99 }
10- return f [amount];
10+ return dp [amount];
1111 }
1212}
Original file line number Diff line number Diff line change 1+ class Solution:
2+ def change(self, amount: int, coins: List[int]) -> int:
3+ dp = [0 for i in range(amount + 1)]
4+ dp[0] = 1
5+ for coin in coins:
6+ for j in range(coin, amount + 1):
7+ dp[j] += dp[j - coin]
8+ return dp[amount]
You can’t perform that action at this time.
0 commit comments