java - Java编程问题，逻辑问题

问题描述

最近我遇到了一个编程问题，例如，给定一个总数和一个输入 k 找到我们可以从 1 到 k 的数字达到总数的方法总数。

例如：总计 = 5，k = 3

输出应该是 5

因为我们可以使用 1、2 和 3 以 5 种方式达到 5，如下所示

1+1+1+1+1

1+1+1+2

1+2+2

1+1+3

2 + 3

我想出了下面的逻辑，但它并没有完全起作用，因为我没有做回溯（我想），我不知道该怎么做

private static int totalways(int total, int k) {
        List<Integer> arr =  new ArrayList();
        for (int i=0; i<total; i++) {
            arr.add(1);
        }
        int count = 1;
        boolean breakLoop = true;
        while (breakLoop) {
            int last = arr.size()-1;
            for (int i=last; i>=1; i--) {
                if (arr.get(i) + arr.get(i-1) <= k) {
                    count++;
                    int sum = arr.get(i) + arr.get(i-1);
                    arr.remove(i-1);
                    arr.remove(i-1);
                    arr.add(sum);
                }
            }
            if (arr.size() == 2){
                breakLoop = false;
            }
        }
        return count;
    }

任何帮助表示赞赏。

标签： javadata-structures

这是一个可以通过动态规划轻松解决的经典问题。另请参阅此类似问题：https ://en.wikipedia.org/wiki/Change-making_problem

第一个观察结果是，当您尝试total使用高达的数字进行书写时k，您可以使用k，也可以不使用k。

如果你用k的话，你还是total - k得用最多的数字k。如果您不使用k，那么您实际上是在total使用高达k-1.

如果我们将 c[total][k] 称为使total数字达到的方式的数量k，那么我们的观察给出了一个公式：c[total][k] = c[total-k][k] + c[total][k-1]。

编辑：这个公式是真的 iff k <= total。如果k > total，那么c[total][k] = c[total][k-1]。

我们还可以观察到c[0][k] = 1对于的所有值k和c[total][0] = 0任何total > 0。

编写一个简单的递归程序来使用我们的递归公式将是可怕的；我们最终会得到指数级的复杂性，因为对于每次调用，我们都需要进行两次递归调用。

相反，我们可以在动态规划算法中使用我们的公式，只需用结果填充一个二维数组c[][]：

int[][] c = new int[total+1][k+1];
for (int n = 1; n <= total; ++n)
{
  c[n][0] = 0;
}
for (int j = 0; j <= k; ++j)
{
  c[0][j] = 1;
}
for (int n = 1; n <= total; ++n)
{
  int maxj = (k <= n) ? k : n;         // maxj = min(k,n)
  for (int j = 1; j <= maxj; ++j)      // case j <= n
  {
    c[n][j] = c[n-j][j] + c[n][j-1];
  }
  for (int j = maxj + 1; j <= k; ++j)  // case j > n
  {
    c[n][j] = c[n][j-1];
  }
}
return c[total][k];

编辑：考虑到案例k > total，根据评论

java - Java编程问题，逻辑问题

问题描述

解决方案

推荐阅读