-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDecodeWays.java
More file actions
94 lines (70 loc) · 2.5 KB
/
DecodeWays.java
File metadata and controls
94 lines (70 loc) · 2.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package Leetcode;
import java.util.Arrays;
public class DecodeWays
{
public static int coinChange( int[] coins, int amount )
{
if( coins == null || coins.length == 0 )
return 0;
// int result = coinChangeHelper( coins, amount, 0 );
int[] dp = new int[ amount + 1 ];
int result = coinChangeHelperBottomUp( coins, amount, dp );
return result == Integer.MAX_VALUE ? -1 : result;
}
private static int coinChangeHelperBottomUp( int[] coins, int amount, int[] dp )
{
if( amount == 0 )
return 0;
Arrays.fill( dp, amount+1 );
dp[0]=0;
for( int t = 1; t <= amount; t++ )
{
for( int c = 0; c <coins.length; c++ )
{
if(t>=coins[c])
dp[t] = Math.min( dp[t], dp[t-coins[c]]+1 );
}
}
return dp[amount]>amount?-1:dp[amount];
}
private static int coinChangeHelperTopDown( int[] coins, int amount, int currentIndex, Integer[][] dp )
{
if( amount == 0 )
return 0;
if( currentIndex >= coins.length || amount < 0 )
return Integer.MAX_VALUE;
int include = Integer.MAX_VALUE;
if( dp[currentIndex][amount] == null )
{
if( coins[currentIndex] <= amount )
{
include = coinChangeHelperTopDown( coins, amount - coins[currentIndex], currentIndex, dp );
if( include != Integer.MAX_VALUE )
include++;
}
int exclude = coinChangeHelperTopDown( coins, amount, currentIndex + 1, dp );
dp[currentIndex][amount] = Math.min( include, exclude );
}
return dp[currentIndex][amount];
}
private static int coinChangeHelper( int[] coins, int amount, int currentIndex )
{
if( amount == 0 )
return 0;
if( currentIndex >= coins.length || amount < 0 )
return Integer.MAX_VALUE;
int include = Integer.MAX_VALUE;
if( coins[currentIndex] <= amount )
{
include = coinChangeHelper( coins, amount - coins[currentIndex], currentIndex );
if( include != Integer.MAX_VALUE )
include++;
}
int exclude = coinChangeHelper( coins, amount, currentIndex + 1 );
return Math.min( include, exclude );
}
public static void main( String[] args )
{
System.out.println( coinChange( new int[]{ 2}, 3 ) );
}
}