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

Question

我在CodeChef和CodeForces上遇到了最小硬币兑换问题。在这两个站点上，我都使用DP提交了我的实现。此实现在两个站点上都存在TLE错误
不幸的是，我找不到此问题的任何其他实现
我正在链接问题-CodeChef-https://www.codechef.com/problems/FLOW005
共同力量-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/贪婪的硬币兑换。pdf