仅使用 1、2、3 步到达第 n 步

Question

几天前我在做一个在线面试，遇到了这个任务，我们可以通过只使用步骤 1 或 2 或 3 来达到第 n 步。

更新的问题：一个孩子正在跑一个有 n 级台阶的楼梯，并且一次可以跳 1 级、2 级或 3 级。实施一种方法来计算孩子可以通过多少种可能的方式跑上楼梯。

这是我使用动态编程的解决方案。但是在面试中，我看到有6个隐藏的测试用例失败了。

public static long countWays(int n)
    {
        if(n==0 || n==1) return 1;

        long[] res = new long[n + 1];
        res[0] = 1;
        res[1] = 1;
        res[2] = 2;
 
        for (int i = 3; i <= n; i++)
            res[i] = res[i - 1] + res[i - 2]
                     + res[i - 3];
 
        return res[n];
    }
 

面试过程中，11个测试用例中只有5个通过，其余6个是隐藏测试用例。

n 的范围是 0 到 10 的 8 次方。

我无法理解我在哪里做错了，这段代码的时间复杂度已经是 O(n)。有没有更好的方法来做到这一点，或者我错过了什么？

Answer 1

你可以写下这个问题的递推关系

S _k = S _k-1 + S _k-2 + S _k-3

以下矩阵形式：

| S[k]   |   | 1  1  1 |   | S[k-1] |   
| S[k-1] | = | 1  0  0 | * | S[k-2] |
| S[k-2] |   | 0  1  0 |   | S[k-3] |   

这意味着k矩阵的-th 次方可以快速为您提供S _k：

            k
| 1  1  1 |     | S[2] |   | S[k+2] | 
| 1  0  0 |   * | S[1] | = | S[k+1] |
| 0  1  0 |     | S[0] |   | S[k]   |

所以要解决这个问题，你基本上需要找到n这个矩阵的-th 次方。

您可以使用平方算法的幂运算及时将某些东西提高到n-th 次方。O(log n)

另一个有用的观察结果是，您只需要 3 个数字S _k、 S _k-1和S _k-2来表示k矩阵的-th 次方：

            k
| 1  1  1 |     | S[k] + S[k-1] + S[k-2]    S[k] + S[k-1]      S[k]   |
| 1  0  0 |   = | S[k]                      S[k-1] + S[k-2]    S[k-1] |
| 0  1  0 |     | S[k-1]                    S[k] - S[k-1]      S[k-2] |

由此，通过乘以矩阵的k-th 和m-th 次幂，您可以得到以下关系：

S _k+m = S _k S _m-2 + S _k-2 S _m + S _k-1 S _m-2 + S _k-2 S _m-1 + S _k-2 S _m-2 + S _k-1 S _m-1
S _k+m-1 = S _k S _m-1 + S _k-1 S _m + S _k-1 S _m-1 + S _k-2 S _m-2
S _k+m-2= S _k-1 S _m-2 + S _k-2 S _m-1 + S _k S _m – S _k-1 S _m-1

将所有这些放在代码中，您将得到以下解决方案：

public class Solution {
    private static final int M = 1_000_000_007;

    // The set of equations for S[k+m], S[k+m-1], S[k+m-2]
    // a[t] is S[k-t] and b[t] is S[m-t]
    private static long[] mul(long[] a, long[] b) {
        long r0110 = a[0]*b[1] + a[1]*b[0];
        long r0011 = a[0]*b[0] + a[1]*b[1];
        return new long[] {
            (a[0]*b[2] + a[2]*b[0] + r0110 + r0011) % M,
            (a[1]*b[2] + a[2]*b[1] + r0011) % M,
            (r0110 + a[2]*b[2] - a[1]*b[1]) % M
        };
    }

    public static long countWays(int n) {
        long[] result = {1, 0, 0};
        long[] square = {1, 0, 0};
        // Exponentiation by squaring
        for (int i = n; i != 0; i /= 2) {
            if (i % 2 == 1) result = mul(result, square);
            square = mul(square, square);
        }
        return result[0];
    }
}