# Java DP O(m*n) Solution

• ``````public class Solution {
public int change(int amount, int[] coins) {
if (coins == null) {
return 0;
}
if (coins.length == 0 && amount == 0){
return 1;
}
if (coins.length == 0) {
return 0;
}

int size = coins.length;
int[][] dp = new int[size][amount + 1];
for (int i = 0; i < size; i++) {
dp[i][0] = 1;
}
for (int j = 1; j < amount + 1; j++) {
if (j % coins[0] == 0) {
dp[0][j] = 1;
} else {
dp[0][j] = 0;
}
for (int i = 1; i < size; i++) {
if (coins[i] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
}
}
}
return dp[size - 1][amount];
}
}
``````

use 1-D array

``````public class Solution {
public int change(int amount, int[] coins) {
if (coins == null) {
return 0;
}
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j < amount + 1; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.