'unsupervised' (we don't know the answer--discovery) or 'supervised' (we know the answer--prediction
- Statistics quantifies numbers
- Data Mining explains patterns
- Machine Learning predicts with models
- Artificial Intelligence behaves and reasons
Quick tips or notes that probably reflects 20 percent of knowledge that usually does 80 percent of job.
3
1
3
7
1
4
44
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 | public class Solution { static void numWays(int n){ //let dp[i] is num ways to reach stair i. //each dp[i] is an accumulation of ways to reach to there int dp[] = new int[n+1]; //assuming you are at nth stair, to reach there //you can step 1 from n-1th stair //or step 2 from n-2th stair or //step 3 from n-3th stair //so you have that many ways to reach to nth stair. //adding them up is the ways to reach to nth stair //dp[3]=dp[2]+dp[1]+dp[0]; /* to reach to stair 1, you have one way:dp[1]=1=dp[0] to reach to stair 2, you have: 1 from dp[0], that is 1 way,2. from dp[1], that's 1 way. to reach to stair 3, you can : 1. dp[0]->dp[3],2.dp[2]->dp[3],3. dp[1]->dp[3] whatever you use to reach dp[2] now contributes to dp[3] */ if(n==1){ System.out.println(1); }else if(n==2){ System.out.println(2); }else{ dp[0]=1;//0 is base dp[1]=1;dp[2]=dp[1]+dp[0]; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } System.out.println(dp[n]); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int s = in.nextInt(); for(int a0 = 0; a0 < s; a0++){ int n = in.nextInt(); numWays(n); } } } |
4 3
1 2 3
4
10 4
2 5 3 6
5
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 | package dp; import java.util.Scanner; /** * first successful story by analyzing it and coming up an algorithm by myself * --even though I saw this question before, I basically forgot. * Them came up a acceptable solution within 15 minutes. * * Cheers to myself. * @author Andrew Ma * */ public class CoinChangeNumOfWays { public static long makeChange(int[] coins, int money) { //I assumes 0 denom having 0 solutions to any amount of money //also assumes any denom having 0 solution to 0 amount of money //it turns out to be right! to be brave to make assumptions! //making room for 0 denom and 0 amount of money long dp[][] = new long[coins.length+1][money+1]; //initialization the known solutions //0 denom for(int i=0;i<money+1;i++){ dp[0][i]=0;//no solution for each money value } //0 money value for(int i=0;i<coins.length+1;i++){ dp[i][0]=0;//no coin can do 0 change } //then build up values towards to final solution //c and m here are for dp array's dimensions /* * define dp[c][m] as accumulated solutions at c and m * dp[c][m]= * 1. dp[c-1][m]. when money value is less than denom, then get solution from last denom * --here it needs to have a 0 denom * 2. dp[c-1][m]+1. when money value equals denom value, we get one more solution * 3. dp[c-1][m] + dp[c][m-coins[c-1]]. when money valus is greater than denom value, * it adds up accumulation from previous denom and same denom for meney value * not including this denom. * damn, when did I become so able to analyze? I guess drawing it out and practice on paper or white board * really helped to see one's thoughts and then you just need to write the code to reflect the thoughts. * and you are confident that you are able to write code to reflect your thoughts. */ for(int c=1;c<coins.length+1;c++){ for(int m=1;m<money+1;m++){ //when it comes to refer values in coins, c need to be converted back to 0 based if(m<coins[c-1]){ //no change at this, copy the last denom's accumulated solutions dp[c][m] = dp[c-1][m]; } else if(m==coins[c-1]){ //we get one more solution dp[c][m] = dp[c-1][m] +1; } else //if (m>coins[c-1]) { //then it is last denom's accumulated solution + lesser value's accumulated solution dp[c][m] = dp[c-1][m] + dp[c][m-coins[c-1]]; } } } return dp[coins.length][money]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int coins[] = new int[m]; for(int coins_i=0; coins_i < m; coins_i++){ coins[coins_i] = in.nextInt(); } System.out.println(makeChange(coins, n)); } } |