优化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

您可以使用这样的缓存(@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;
}

Answer 2

这是动态规划的经典问题。创建一个大小为n的数组(其中n是您要寻找的数字)，然后按您的方式返回，通过增加获取值的方式来更新数组。这样，您就可以使用O(n)复杂性(目前的复杂性是指数级的)。