优化 java 方法（根据骰子找到到达点的所有方法）

Question

我用这个方法来解决我需要根据骰子从 (1-6) 迈出一步并计算到达距离的所有可能方式来覆盖一段距离的问题我做了这个方法

static int watchCount(int distance)
{
    // Base cases
    if (distance<0) return 0;
    if (distance==0) return 1;

    return watchCount(distance-1) +
        watchCount(distance-2) +
        watchCount(distance-3)+
        watchCount(distance-4) +
        watchCount(distance-5)+
        watchCount(distance-6);

}

但对于像 >500 这样的大值，此方法需要很长时间才能帮助优化。谢谢

Answer 1

这是动态规划的经典问题。创建一个大小为 n 的数组（其中 n 是您要查找的数字）并返回，通过增加获取值的方法数来更新数组。这样，您可以在 O(n) 复杂度中完成（目前复杂度是指数级的）。

Answer 2

您可以像这样使用缓存（与@PiotrWilkin 的想法相同）：

static int watchCount(int distance, Integer[] cache) {
    // Base cases
    if (distance < 0) {
        return 0;
    }
    if (distance == 0) {
        return 1;
    }
    if (cache[distance-1] == null) {
        cache[distance-1] = watchCount(distance - 1, cache)
                + watchCount(distance - 2, cache)
                + watchCount(distance - 3, cache)
                + watchCount(distance - 4, cache)
                + watchCount(distance - 5, cache)
                + watchCount(distance - 6, cache);
    }
    return cache[distance-1];
}

编辑迭代实现：

public static int iterativeWatchCount(int n) {
    if (n < 0) {
        return 0;
    }
    int index = 0;
    int[] cache = new int[6];
    cache[cache.length - 1] = 1;
    int sum = 1;
    for (int i = 0; i < n; i++, index = (index + 1) % cache.length) {
        sum = cache[0] + cache[1] + cache[2] + cache[3] + cache[4] + cache[5];
        cache[index] = sum;
    }
    return sum;
}

优化 java 方法（根据骰子找到到达点的所有方法）

optimize java method (finding all ways to reach a point on basis of dice)

java

optimization

tail-recursion