Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def f(ms: List[Int], n: Int): Int = ms match {
- case h :: t =>
- if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
- case _ => 0
- }
- val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)
- final static int TOTAL = 200;
- public static void main(String[] args) {
- int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
- int[] ways = new int[TOTAL + 1];
- ways[0] = 1;
- for (int coin : coins) {
- for (int j = coin; j <= TOTAL; j++) {
- ways[j] += ways[j - coin];
- }
- }
- System.out.println("Result: " + ways[TOTAL]);
- }
- class IterationForCoin(stream: Stream[Int], coin: Int) {
- val (lower, higher) = stream splitAt coin
- val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b })
- }
- val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
- val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) =>
- new IterationForCoin(stream, coin).next
- } last
- import scalaz._
- import Scalaz._
- val memo = immutableHashMapMemo[(List[Int], Int), Int]
- def f(ms: List[Int], n: Int): Int = ms match {
- case h :: t =>
- if (h > n) 0 else if (n == h) 1 else memo((f _).tupled)(ms, n - h) + memo((f _).tupled)(t, n)
- case _ => 0
- }
- val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)
Add Comment
Please, Sign In to add comment