CodeChef 和 CodeForces 上的最小硬币找零问题（动态编程实现）超过时间限制

Question

我在 CodeChef 和 CodeForces 上遇到了最小硬币找零的问题。在这两个站点上，我都使用 DP 提交了我的实现。此实现在两个站点上都给出了 TLE 错误。
不幸的是，我找不到这个问题的任何其他实现。
我正在联系问题 - CodeChef-https://www.codechef.com/problems/FLOW005
CodeForces - https://codeforces.com/problemset/problem/996/A
这是我的代码（CodeChef 实现）-

int main() {
    int T{};
    std::cin >> T;
    for (int i = 1; i <= T; ++i) {
        int N{};
        std::cin >> N;
        std::vector <int> arr(N + 1);
        for (int i = 0; i < N + 1; ++i) {
            arr[i] = minCoins(i, arr);
        }
        std::cout << arr[N] << std::endl;
    }

    return 0;
}

minCoins 函数 -

int minCoins(int x, std::vector <int> arr) {
    if (x == 0)
        return 0;
    else if (x == 1 || x == 2 || x == 5 || x == 10 || x == 50 || x == 100)
        return 1;
    int min{ 1 + arr[x - 1]};
    if (x > 100)
        min = std::min(min, l + arr[x - 100]);
    if (x > 50)
        min = std::min(min, 1 + arr[x - 50]);
    if (x > 10)
        min = std::min(min, 1 + arr[x - 10]);
    if (x > 5)
        min = std::min(min, 1 + arr[x - 5]);
    if (x > 2)
        min = std::min(min, 1 + arr[x - 2]);
    if (x > 1)
        min = std::min(min, 1 + arr[x - 1]);
    return min;
}

阅读约束后选择了int数据类型，不存在整数溢出问题。另外，如果有人想建议我如何删除 if 梯子并用更简单的东西替换它，我将不胜感激。另外，感谢您花时间阅读我的问题:)

Answer 1

#include <iostream>

int main() {
  int tests;
  std::cin >> tests;

  int value;
  while (tests--) {
    int coinCount = 0;
    std::cin >> value;
    while (value > 0) {
      if (value >= 100) {
        coinCount += (value / 100);
        value %= 100;
      } else if (value >= 50) {
        coinCount += (value / 50);
        value %= 50;
      } else if (value >= 10) {
        coinCount += (value / 10);
        value %= 10;
      } else if (value >= 5) {
        coinCount += (value / 5);
        value %= 5;
      } else if (value >= 2) {
        coinCount += (value / 2);
        value %= 2;
      } else if (value >= 1) {
        coinCount += (value / 1);
        value = 0;
      }
    }
    std::cout << coinCount << '\n';
  }
}

在 CodeChef 上测试并通过，执行时间为 0.00。问题中显示的货币系统的设计方式使得贪心选择是正确的选择。这适用于几乎所有现有货币系统。

如果您需要证明，http://www.cs.toronto.edu/~denisp/csc373/docs/greedy-coin-change.pdf

CodeChef 和 CodeForces 上的最小硬币找零问题（动态编程实现）超过时间限制

Time limit exceeded on minimum coin change problem(Dynamic Programming Implementation) on CodeChef and CodeForces

c++

algorithm

dynamic-programming