这是本演示文稿中给出的问题。 Dynamic Programming
现在我已经使用递归实现了该算法，它适用于小值。但是当 n 大于 30 时，它变得非常慢。演示文稿提到对于 n 的大值，应该考虑类似于 the matrix form of Fibonacci numbers .我无法理解如何使用斐波那契数列的矩阵形式来提出解决方案。有人能给我一些提示或伪代码吗
谢谢
最佳答案
是的，您可以使用快速斐波那契实现中的技术在时间 O(log n) 内解决此问题!方法如下。
让我们按照问题陈述中的定义，即 1 + 3 与 3 + 1 计算相同。那么您有以下递归关系:
- A(0) = 1
- A(1) = 1
- A(2) = 1
- A(3) = 2
- A(k+4) = A(k) + A(k+1) + A(k+3)
这里的矩阵技巧是注意
| 1 0 1 1 | |A( k )| |A(k) + A(k-2) + A(k-3)| |A(k+1)|
| 1 0 0 0 | |A(k-1)| | A( k ) | |A( k )|
| 0 1 0 0 | |A(k-2)| = | A(k-1) | = |A(k-1)|
| 0 0 1 0 | |A(k-3)| | A(k-2) | = |A(k-2)|
换句话说，将系列中最后四个值的向量相乘生成一个向量，其中这些值向前移动一步。
我们将该矩阵称为 M。然后注意
|A( k )| |A(k+2)|
|A(k-1)| |A(k+1)|
M^2 |A(k-2)| = |A( k )|
|A(k-3)| |A(k-1)|
换句话说，乘以该矩阵的平方会将级数向下移动两步。更一般地说:
|A( k )| | A(k+n) |
|A(k-1)| |A(k-1 + n)|
M^n |A(k-2)| = |A(k-2 + n)|
|A(k-3)| |A(k-3 + n)|
因此乘以 Mn 会将级数向下移动 n 步。现在，如果我们想知道 A(n+3) 的值，我们可以计算
|A(3)| |A(n+3)|
|A(2)| |A(n+2)|
M^n |A(1)| = |A(n+1)|
|A(0)| |A(n+2)|
然后读出向量的顶部条目!这可以通过平方取幂在时间 O(log n) 内完成。这里有一些代码可以做到这一点。这使用 a matrix library I cobbled together a while back :
#include "Matrix.hh"
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
/* Naive implementations of A. */
uint64_t naiveA(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
if (n == 2) return 1;
if (n == 3) return 2;
return naiveA(n-1) + naiveA(n-3) + naiveA(n-4);
}
/* Constructs and returns the giant matrix. */
Matrix<4, 4, uint64_t> M() {
Matrix<4, 4, uint64_t> result;
fill(result.begin(), result.end(), uint64_t(0));
result[0][0] = 1;
result[0][2] = 1;
result[0][3] = 1;
result[1][0] = 1;
result[2][1] = 1;
result[3][2] = 1;
return result;
}
/* Constructs the initial vector that we multiply the matrix by. */
Vector<4, uint64_t> initVec() {
Vector<4, uint64_t> result;
result[0] = 2;
result[1] = 1;
result[2] = 1;
result[3] = 1;
return result;
}
/* O(log n) time for raising a matrix to a power. */
Matrix<4, 4, uint64_t> fastPower(const Matrix<4, 4, uint64_t>& m, int n) {
if (n == 0) return Identity<4, uint64_t>();
auto half = fastPower(m, n / 2);
if (n % 2 == 0) return half * half;
else return half * half * m;
}
/* Fast implementation of A(n) using matrix exponentiation. */
uint64_t fastA(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
if (n == 2) return 1;
if (n == 3) return 2;
auto result = fastPower(M(), n - 3) * initVec();
return result[0];
}
/* Some simple test code showing this in action! */
int main() {
for (int i = 0; i < 25; i++) {
cout << setw(2) << i << ": " << naiveA(i) << ", " << fastA(i) << endl;
}
}
现在，如果 3 + 1 和 1 + 3 被视为等价，这会发生什么变化？这意味着我们可以考虑通过以下方式解决这个问题:
- 设 A(n) 为将 n 写为 1、3 和 4 之和的方法数。
- 令 B(n) 为将 n 写为 1 和 3 之和的方法数。
- 令 C(n) 为将 n 写为 1 之和的方法数。
然后我们有以下内容:
- 对于所有 n ≤ 3，A(n) = B(n)，因为对于该范围内的数字，唯一的选择是使用 1 和 3。
- A(n + 4) = A(n) + B(n + 4)，因为您的选择是 (1) 使用 4 或 (2) 不使用 4，剩下的总和使用 1 和3 秒。
- 对于所有 n ≤ 2，B(n) = C(n)，因为对于该范围内的数字，唯一的选择是使用 1。
- B(n + 3) = B(n) + C(n + 3)，因为您的选择是 (1) 使用 3 或 (2) 不使用 3，剩下的总和仅使用 1 .
- C(0) = 1，因为只有一种方法可以将 0 写成无数之和。
- C(n+1) = C(n)，因为用 1 写东西的唯一方法是取出一个 1，然后将剩余的数字写为 1 的和。
要理解的内容很多，但请注意以下几点:我们最终关心的是 A(n)，要对其进行评估，我们只需要知道 A(n)、A(n-1) 的值， A(n-2), A(n-3), B(n), B(n-1), B(n-2), B(n-3), C(n), C(n-1) )、C(n-2) 和 C(n-3)。
例如，假设我们知道 n 的某个固定值的这十二个值。我们可以为 n 的下一个值学习这十二个值，如下所示:
C(n+1) = C(n)
B(n+1) = B(n-2) + C(n+1) = B(n-2) + C(n)
A(n+1) = A(n-3) + B(n+1) = A(n-3) + B(n-2) + C(n)
然后剩余的值向下移动。
我们可以将其表述为一个巨大的矩阵方程:
A( n ) A(n-1) A(n-2) A(n-3) B( n ) B(n-1) B(n-2) C( n )
| 0 0 0 1 0 0 1 1 | |A( n )| = |A(n+1)|
| 1 0 0 0 0 0 0 0 | |A(n-1)| = |A( n )|
| 0 1 0 0 0 0 0 0 | |A(n-2)| = |A(n-1)|
| 0 0 1 0 0 0 0 0 | |A(n-3)| = |A(n-2)|
| 0 0 0 0 0 0 1 1 | |B( n )| = |B(n+1)|
| 0 0 0 0 1 0 0 0 | |B(n-1)| = |B( n )|
| 0 0 0 0 0 1 0 0 | |B(n-2)| = |B(n-1)|
| 0 0 0 0 0 0 0 1 | |C( n )| = |C(n+1)|
让我们在这里称这个巨大的矩阵为 M。然后如果我们计算
|2| // A(3) = 2, since 3 = 3 or 3 = 1 + 1 + 1
|1| // A(2) = 1, since 2 = 1 + 1
|1| // A(1) = 1, since 1 = 1
M^n |1| // A(0) = 1, since 0 = (empty sum)
|2| // B(3) = 2, since 3 = 3 or 3 = 1 + 1 + 1
|1| // B(2) = 1, since 2 = 1 + 1
|1| // B(1) = 1, since 1 = 1
|1| // C(3) = 1, since 3 = 1 + 1 + 1
我们将得到一个向量，其第一个条目是 A(n+3)，即将 n+3 写为 1、3 和 4 之和的方法数。 (我实际上已经对此进行了编码以检查它 - 它有效!)然后您可以使用使用矩阵计算斐波纳契数的技术，以有效地计算斐波纳契数，以便在时间 O(log n)中解决这个问题。
下面是一些代码:
#include "Matrix.hh"
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
/* Naive implementations of A, B, and C. */
uint64_t naiveC(int n) {
return 1;
}
uint64_t naiveB(int n) {
return (n < 3? 0 : naiveB(n-3)) + naiveC(n);
}
uint64_t naiveA(int n) {
return (n < 4? 0 : naiveA(n-4)) + naiveB(n);
}
/* Constructs and returns the giant matrix. */
Matrix<8, 8, uint64_t> M() {
Matrix<8, 8, uint64_t> result;
fill(result.begin(), result.end(), uint64_t(0));
result[0][3] = 1;
result[0][6] = 1;
result[0][7] = 1;
result[1][0] = 1;
result[2][1] = 1;
result[3][2] = 1;
result[4][6] = 1;
result[4][7] = 1;
result[5][4] = 1;
result[6][5] = 1;
result[7][7] = 1;
return result;
}
/* Constructs the initial vector that we multiply the matrix by. */
Vector<8, uint64_t> initVec() {
Vector<8, uint64_t> result;
result[0] = 2;
result[1] = 1;
result[2] = 1;
result[3] = 1;
result[4] = 2;
result[5] = 1;
result[6] = 1;
result[7] = 1;
return result;
}
/* O(log n) time for raising a matrix to a power. */
Matrix<8, 8, uint64_t> fastPower(const Matrix<8, 8, uint64_t>& m, int n) {
if (n == 0) return Identity<8, uint64_t>();
auto half = fastPower(m, n / 2);
if (n % 2 == 0) return half * half;
else return half * half * m;
}
/* Fast implementation of A(n) using matrix exponentiation. */
uint64_t fastA(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
if (n == 2) return 1;
if (n == 3) return 2;
auto result = fastPower(M(), n - 3) * initVec();
return result[0];
}
/* Some simple test code showing this in action! */
int main() {
for (int i = 0; i < 25; i++) {
cout << setw(2) << i << ": " << naiveA(i) << ", " << fastA(i) << endl;
}
}
关于algorithm - 使用矩阵找出将 n 写为 1、3 和 4 之和的不同方式的数量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41111249/