1

我正在自学动态编程。这几乎是神奇的。不过实话说。无论如何，我解决的问题是：Given a stairs of N steps and a child who can either take 1, 2, or 3 steps at a time, how many different ways can the child reach the top step?。问题并不难，我的实现如下。

import java.util.HashMap;

public class ChildSteps {
    private HashMap<Integer, Integer> waysToStep;

    public ChildSteps() {
        waysToStep = new HashMap<Integer, Integer>();
    }

    public int getNthStep(int n) {
        if (n < 0) return 0; // 0 ways to get to a negative step

        // Base Case
        if (n == 0) return 1;

        // If not yet memorized
        if (!waysToStep.containsKey(n)) {
            waysToStep.put(n, getNthStep(n - 3) + getNthStep(n - 2) + getNthStep(n - 1));
        }

        return waysToStep.get(n);
    }
}

但是，现在我想获得运行时。我该如何解决这个问题？我对 Akra-Bazzi 和 Master Theorem 很熟悉（仅此而已）。这些在这里适用吗？

http://en.wikipedia.org/wiki/Master_theorem

在这里它似乎可能是：T(N) = 3 * T(???) + O(1)但我真的不确定。

多谢你们。

4

1 回答 1

1

在最坏的情况分析中，它将是：

T(N) = N * (containsKey(N) + 8)

假设 containsKey = N （可能是N^2或Log(N)）那么这简化为T(N) = N。

您必须找出函数containsKey(N)以获得实际方程。

不过，您真的想多了；您无需为此进行算法分析。给你的好报价：“过早的优化是万恶之源”

于 2012-02-02T02:34:11.173 回答