给定车轮总数，组成两轮和四轮车辆的方法数

Question

我在一次采访中被问到这个问题。

给定一个表示车轮总数的整数，以及无限供应的两轮和四轮车辆，有多少种方法可以组成一个车队，使得车辆的车轮总数正好是给定的。当且仅当它们包含不同数量的两轮和四轮车辆时，两种选择车辆的方式被认为是不同的。

例如，如果输入数组是[4, 5, 6]，则应返回[2, 0, 2]。个别情况下，我们可以有 1 辆四轮车或 2 辆两轮车有 4 个轮子。我们不能有 5 个轮子。在最后的情况下，我们可以有 1 个四轮和 1 个两轮，或 3 个两轮。

我的解决方案很简单：给定轮子，形成车队的方法数量dp[i] = dp[i - 2] + dp[i - 4]在哪里。dp[i]i

但它没有通过测试用例。我做错了什么？

Answer 1

尝试这个。

public static void main(String args[]) throws IOException {
    int[] input = {4, 5, 6, 0};
    int[] output = IntStream.of(input)
        .map(n -> n <= 0 || n % 2 != 0 ? 0 : n / 4 + 1)
        .toArray();
    System.out.println(Arrays.toString(output));
}

输出：

[2, 0, 2, 0]

1. 当n为奇数时，结果始终为零。
2. 当n是偶数时，您最多可以拥有n / 4四轮车辆。每辆都可以兑换两辆两轮车，所以箱数是总的数量{n / 4, ... , 2, 1, 0}。那就是n / 4 + 1。但是需要注意的是，当 时n <= 0，它变成 0。