使用矩阵来查找写入n的不同方式的数量,即1,3和4的总和？

Question

这是本演示文稿中给出的问题.动态编程

现在我已经使用递归实现了算法,它适用于小值.但是当n大于30时,它变得非常慢.该演示文稿提到,对于n的大值,应该考虑类似于Fibonacci数的矩阵形式的东西 .我很难解决如何使用Fibonacci数的矩阵形式来一个解决方案.可以给我一些提示或伪代码

谢谢

Answer 1

是的,你可以使用快速Fibonacci实现的技术在时间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)|

换句话说,将序列中最后四个值的向量相乘会产生一个向量,其值向前移动一步.

我们在那里称那个矩阵.然后注意到

     |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)|

因此,乘以M ⁿ将系列向下移动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)中完成.这里有一些代码可以做到这一点.这使用了我前后拼凑在一起的矩阵库:

#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写为1s,3s和4s之和的方式的数量.
• 设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,剩下的总和只使用1s.
• 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的某个固定值的这12个值.我们可以为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的总和.(我实际上已对此进行了编码以检查它 - 它的工作原理!)然后,您可以使用该技术使用矩阵计算斐波纳契数,并使用Fibonacci数来有效地在时间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;
  }
}