SCALA Exercise 3: Counting Change

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.
Do this exercise by implementing the countChange function inMain.scala. This function takes an amount to change, and a list of unique denominations for the coins. Its signature is as follows:










1































def countChange(money: Int, coins: List[Int]): Int
Once again, you can make use of functions isEmpty, head and tail on the list of integers coins.
Hint: Think of the degenerate cases. How many ways can you give change for 0 CHF(swiss money)? How many ways can you give change for >0 CHF, if you have no coins?
def countChange(money: Int, coins: List[Int]): Int = {
  if(money == 0)
    1
  else if(money > 0 && !coins.isEmpty)
    countChange(money - coins.head, coins) + countChange(money, coins.tail)
  else
    0
}
这个Hint给出了基本情况，即
1.money>0且没有coins的情况
2.money=0的情况
以以上两个情况为出口，写递归。
recursion的两种情况：
1.countChange(money - coins.head, coins)


要么使用第一种面额的钱来凑money


2.countChange(money, coins.tail)


要么用其它面额的钱来凑money


总的情况为上述两种情况相加。




对于money=4，coins为[1,2]的情况，递归的过程基本是这样的：


1,1,1,1


1,1,1,2 减完为为负数，排除


1,1,2


1,2,2 剪完为负数，排除


2,2












2 





Could you provide some intuition behind this solution? – user2253546 Apr 4 '17 at 8:01






4 





The idea here is to use up our coins and subtract it from the current amount of money. Eventually, the amount of money will be either 0, some negative number (meaning this combination of coins failed), or some positive number (meaning that we can still subtract more with the coins we currently have). countChange(money - coins.head, coins) will exhaust all combinations subtracting the first coin from the money, while countChange(money, coins.tail) exhausts all combinations using all other coins only. They are added together, since + is synonymous with the logical OR operator. – rkenmi May 6 '17 at 6:01 






1 





The solution is nice. One question about the base case: what if the initial money is 0. Isn't there 0 way to make changes for 0 money? – rileyss Sep 13 '17 at 7:49






   





Imagine that you are given some coins in front of you and you are asked to match that using a huge bag of coins. If you had a penny in front of you, there is only 1 way to match that; by using a penny from your bag. Next, what if you had no coins in front of you? Again there is only 1 way to represent that; by not taking out any coins in your bag. Now finally, what if you had negative money? Well, you can't really represent that physically. So there are 0 ways to produce this output; the bag of coins is completely irrelevant in this scenario. – rkenmi Nov 3 '17 at 3:55


















































评论











发表评论























此博客中的热门博文









232. Implement Queue using Stacks





















MA:  class MyQueue {      Stack<Integer> simQ=new Stack<Integer>();      Stack<Integer> buffer=new Stack<Integer>();      /** Initialize your data structure here. */      public MyQueue() {      }           /** Push element x to the back of queue. */      public void push(int x) {          simQ.push(x);      }           /** Removes the element from in front of queue and returns that element. */      public int pop() {          while(!simQ.empty()){              buffer.push(simQ.pop());          }          int temp=buffer.pop();          while(!buffer.empty()){              simQ.push(buffer.pop());          }          return temp;      }  ...








阅读全文










496. Next Greater Element I





















MA:  class Solution {      public int[] nextGreaterElement(int[] nums1, int[] nums2) {          int[] nums3=new int[nums1.length];          for(int i=0;i<nums1.length;i++){              int max=-1;              nums3[i]=max;              int target=nums1[i];              boolean findTarget=false;              for(int j=0;j<nums2.length;j++){                  if(nums2[j]==nums1[i] && findTarget==false){                      findTarget=true;                      continue;                  }                  if(nums2[j]>target&&findTarget==true){  ...








阅读全文










20. Valid Parentheses





















OA:  class  Solution  {     public  boolean  isValid (String s)  {         char [] stack = new  char [s.length()];         int  head = 0 ;         for  ( char  c : s.toCharArray()) {             if  (c == '(' ) {                 stack[head++] = c;             } else  if  (c == '[' ) {                 stack[head++] = c;             } else  if  (c == '{' ) {                 stack[head++] = c;             } else  if  (c == ')' ) {                 if  (head == 0 ) return  false ;                 if  (stack[--head] != '(' ) return  false ;             } else  if  (c == ']' ) {                 if  (head == 0 ) return  false ;                 if  (stack[--head] != '[' ) return  false ;             } else  if  (c == '}' ) {                 if  (head == 0 ) return  false ;                 if  (stack[--head] != '{' ) return  false ;             }         }         return  head == 0 ;     } }  OA比MA快一倍。  String有个toCharArray()...








阅读全文