java - 带内存的循环内递归的运行时复杂度

Question

我想知道如何确定以下代码的时间复杂度，使用带内存的自顶向下动态规划方法(注意 i、k、d 可以是任何整数值):

solve(i, k, d) {
    if (k >= d) {
        A[i][k] = 0;
        return 0;
    }

    if (i == 0) {
        A[i][k] = 0;
        return 0;
    }

    if (A[i][k] == null) {
        for (int j = 0; j < k + 1; j++) {
            A[i][k] = solve(i - 1, (k + 1 - j), d);
        }
    }

    return A[i][k];
}

Answer 1

问题:

solve(i - 1, (k + 1 - j), d)

当 j = 0 时会给出越界错误，因为 A 索引应该从 0 到 K [K 是最大索引]

---

答案:该函数的复杂度为 O(n * n)。

---

直觉:

(很明显，最坏的情况是没有解决方案，所以我专注于此)

由于递归调用是在将值放入内存缓存之前进行的，因此最后(最短)的后缀将首先被缓存。这是因为该函数首先使用长度为 N 的数组调用，然后使用长度为 N-1 的数组调用自身，然后......，使用缓存并返回的 len 0 数组，然后是长度为 1 的数组被缓存并返回，...，长度为 N 的数组被缓存并返回。

解释:

假设矩阵的大小为 I x K 并考虑最坏的情况，

[注意]在最坏的情况下，函数调用将从矩阵的右下角开始

初始化发生在两种情况下:

• k >= d
• 我== 0

[注意] 在最坏的情况下，k 总是小于d。

For loop for `(I, K)`
- Recursion call `for (i-1, k:[K to 0])` 
- Update value for `A[i, k]`

[注意] i = 0 是函数初始化 A 并返回 0 的基本情况。