相关疑难解决方法(0)

假设S = 5且N = 3,解决方案看起来像 - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> < 2,3,0> <3,2,0> <1,2,2>等

在一般情况下,N个嵌套循环可用于解决问题.运行N嵌套循环,在它们内部检查循环变量是否加到S.

如果我们提前不知道N,我们可以使用递归解决方案.在每个级别中,运行从0到N的循环,然后再次调用函数本身.当我们达到N的深度时,看看获得的数字是否加起来为S.

其他动态编程解决方案？

我遇到了这个问题:

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

给定值N,如果我们想要改变N美分,并且我们每个S = {S1,S2,..,Sm}值硬币都有无限供应,我们可以通过多少方式进行更改？硬币的顺序无关紧要.

例如,对于N = 4和S = {1,2,3},有四个解:{1,1,1,1},{1,1,2},{2,2},{1, 3}.因此输出应为4.对于N = 10且S = {2,5,3,6},有五种解决方案:{2,2,2,2,2},{2,2,3,3}, {2,2,6},{2,3,5}和{5,5}.所以输出应该是5.

我提出了解决方案:

// recurrence relation
count[N] = count[N-d] for all denomination <= N

Source code
-----------

public static int numWays(int N, int[] denoms) {
  if (N == 0)
     return 0;

  int[] ways = new int[N+1];
  ways[0] = 1;

  for (int i=1; i<=N; i++) {
     ways[i] = 0;
     for (int d : denoms) {
        if (d <= i) {
           ways[i] += ways[i-d];
        }
     }
  }

  return …