乐趣区

关于算法:庖丁解牛斐波拉契数列和背包问题详细解析两个问题优化过程带你从最基本核心的问题看懂动态规划

jiezi

庖丁解牛斐波拉契数列和背包问题——具体解析两个问题优化过程，带你从最根本的问题看懂动静布局！！！

动静布局作为一种十分经典的一类算法，不仅在解决理论问题当中有很多理论的利用，同时通常也是面试的一个重点。本篇文章一步步分析动静布局的基本原理，通过 斐波拉契数列问题 （优化工夫复杂度从 $O(2^n)$ 到O(n) 再到 O(log(n))）和经典的01 背包问题 一步一步带你从最根本的原理弄懂动静布局。咱们首先剖析斐波拉契数列问题，而后在剖析问题的时候缓缓的深刻动静布局。

本篇文章的篇章构造：

斐波拉契数列

斐波拉契数列的定义如下（如果公式不能很好的渲染，请查看这篇同样内容而且可能渲染公式的文章）：

$$
F_0 = 0
$$

$$
F_1 = 1
$$

$$
F_n = F_{n – 1} + F_{n- 2}
$$

就是斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。比如说在斐波拉契数列当中第一个数为 0，第二个数为 1，因而第三个数为后面两个数之和，因而第三个数为 1，同理第四个数是第二个数和第三个数之和，因而第四个数为 2，上面就是斐波拉契数的变动：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ....

斐波拉契数列——递归法

当初咱们的问题是要你求第 n 个斐波拉契数，这个问题还是比较简单的，很容易想到这就是一个能够递归解决的问题，在公式 $F_n = F_{n – 1} + F_{n-2}$ 当中也容易看出应该应用递归。当初要确定的就是递归终止条件。

  • 如果 n == 0 则返回 0，如果 n == 1 则返回 1，这就是递归终止条件。

确定完递归终止条件之后咱们很容易写出上面这样的代码：

public class Fibonacci {public static int fibonacci(int n) {if (n <= 1)
      return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
  }

  public static void main(String[] args) {System.out.println(fibonacci(6));
  }
}

当咱们求第 6 个斐波拉契数的时候，函数 fibonacci 的调用过程如下所示：

咱们在调用 fibonacci(6) 的时候他会调用：[fibonacci(5)和 fibonacci(4)]，而后 fibonacci(5) 会调用 [fibonacci(4) 和 fibonacci(3)]，fibonacci(4)会调用 [fibonacci(3) 和 fibonacci(2)]……

咱们容易发现咱们在函数调用的过程当中存在反复，比方下图两个雷同的局部示意对 fibonacci(4) 从新计算，因为他们的调用树都是一样的：

这种应用递归的形式计算斐波拉契数列的工夫和空间复杂度都是 $O(2^n)$。

斐波拉契数列——数组法优化工夫复杂度

既然是反复计算那么咱们是否可用防止 反复计算 呢？在计算机一种常见的做法就是 空间换工夫 ，咱们能够将之前计算的数据存下来，比方咱们用数组fib[] 存储咱们计算失去的后果，fib[i] = fibonacci(i) ，那么依据斐波拉契数列的公式咱们能够晓得：

$$
fib[i] = fib[i – 1] + fib[i – 2], i \ge 2
$$

当咱们通过数组存储两头计算的数据的时候，咱们应该应用什么样的算法进行计算呢？

在下面的图片当中比方咱们要计算 绿色框 对应的数据，依据公式：

$$
fib[i] = fib[i – 1] + fib[i – 2], i \ge 2
$$

咱们晓得 绿色框 依赖它后面的两个数据，因而咱们在计算 fib[i] 的时候，须要提前将后面两个它依赖的数据计算好，因而咱们能够从左至右计算 fib 数组，这样的话咱们在计算第 n 个fib数的时候后面 n - 1 个fib数曾经计算好了。

因而咱们的代码能够像上面这样：

public static int fibonacci(int n) {if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    // 进行初始化操作
    fib[0] = 0;
    fib[1] = 1;
    // 从前往后遍历失去 fib 数组的后果
    for (int i = 2; i <= n; i++) {fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

这种形式咱们失去的工夫和空间复杂度都降为了O(n)。

斐波拉契数列——数组法优化空间复杂度

依据下面的剖析咱们能够晓得，咱们在计算第 n 个斐波拉契数的时候仅仅依赖它后面的两个数据，因而咱们无需用一个数据将所有的数据都保留下来，咱们能够只用两个变量保留他后面的两个值即可，而后在进行 for 循环 的时候一直进行更新就行了。

public static int fibonacci(int n) {if (n <= 1)
        return n;
    // 进行初始化操作
    int a = 0;
    int b = 1;
    int fib = 0;
    // 从前往后遍历失去 fib 的后果
    for (int i = 2; i <= n; i++) {
        fib = a + b;
        a = b;
        b = fib;
    }
    return fib;
}

这样咱们的工夫复杂度为 O(n) 空间复杂度就升高到了O(1)。

斐波拉契数列——矩阵乘法优化工夫复杂度

咱们曾经晓得斐波拉契数列的公式为：

$$
fib[i] = fib[i – 1] + fib[i – 2], i \ge 2
$$

$$
fib[n + 2] = fib[i + 1] + fib[i]
$$

又因为：

$$
fib[n + 1] = fib[n + 1]
$$

依据下面的公式，咱们依据矩阵乘法原理能够失去：

咱们将 n - 1 失去：

咱们不停的对上式最右侧公式进行开展能够失去

从上式看，咱们如果想求 fib[n] 的值，须要计算矩阵的幂，如果咱们间接计算的话，工夫复杂度为达到O(n)，然而咱们心愿可能将工夫复杂度升高到O(log(n))。在正式求解矩阵幂之前，咱们先思考一个问题，如何在计算 $a^n$ 时将工夫复杂度升高到O(log(n))。

疾速计算整数幂

首先咱们先明确咱们的指标：在计算 $a^n$ 时将工夫复杂度升高到O(log(n))。这个问题咱们能够间接应用一个循环就能够解决，然而工夫复杂度为O(n)：

  /**
   * 这个函数的目标是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
    public static int pow(int base, int n) {
        int ans = 1;
        for (int i = 0; i < n; i++)
            ans *= base;
        return ans;
    }

咱们晓得计算机在进行运算的时候都是采纳 2 进制 进行运算，所有的正整数如果是 2 的整数次幂的话，数据的二进制当中只有一个为为1，其余地位为0。

咱们晓得一个数据用二进制示意只有某些地位为 0，某些地位为 1，那么一个整数肯定能够用若干个整数相加失去，而且这些整数满足 2 的整数次幂，比方下图中的7 = 1 + 2 + 4：

同样的咱们须要求解的 $2^n$ 上的 n 也是能够通过加法失去，比如说 $2^7 = 2^1 * 2^2 * 2^4 = 2^{(1 + 2 + 4)}$，因而咱们能够应用上面的代码进行疾速幂的求解：

  /**
   * 这个函数的目标是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
  public static int power(int base, int n) {if (n == 0) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 这个右移的目标是查看 n 第 i 个比特地位上是否为 1 如果为 1 就须要进行乘法运算
      // 这就相当于 ans *= base^i
      if (((n >> i) & 1) == 1) {ans *= base; // 这就相当于 幂相加 能够仔细分析下面的 2^7 的运算形式}
      // base 的变动状况为 base^1, base^2, base^3, base^4, ...
      // 比如说当 base 为 2 时，base 的变动状况为 1, 2, 4, 8, 16, 32, 64, ...
      base *= base;
    }
    return ans;
  }

斐波拉契数据列矩阵乘法的疾速幂

首先在咱们计算当中须要进行一个 2x2 的矩阵乘法运算，首先咱们先定义一个简略的 2x2 矩阵乘法运算。

  /**
   * 这里为了简略期间，因为咱们的矩阵乘法是 2x2 的
   * 所以能够间接做这样的简略的乘法
   * @param a
   * @param b
   * @return
   */
  public static int[][] matrixMultiply(int[][] a, int[][] b) {int[][] ans = new int[2][2];
    ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
    ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
    ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
    ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
    return ans;
  }

咱们当初来看咱们应用矩阵疾速幂失去斐波拉契数列的后果：

public static int fibonacci(int n) {if (n <= 1) return n;
    // 这个函数的作用是失去后面提到的矩阵的 n 次幂的后果
    int[][] mm = fibMatrixPower(n); // 这个函数的具体实现在上面
    // 依据下图当中的公式容易晓得咱们最终返回的后果就是 mm[1][0] 因为 fib[1] = 1 fib[0] = 0
    return mm[1][0];
}

public static int[][] fibMatrixPower(int n) {
    // 这个矩阵是依据上图咱们的公式失去的
    int[][] baseMatrix = {{1, 1}, {1, 0}};
    if (n == 1)
        return baseMatrix;
    // 初始化为单位矩阵 如果是整数幂 初始化为 1
    // 这里初始化为单位矩阵的目标是因为单位矩阵和任何矩阵
    // 相乘后果都为原矩阵
    int[][] ans = {{1, 0}, {0, 1}};

    for (int i = 0; i < n; i++) {
        // 这个右移的目标是查看 n 对应的地位上是否为 1 如果为 1 就须要进行矩阵乘法运算
        if (((n >> i) & 1) == 1) {
            // 进行矩阵乘法运算 相当于整数幂的时候数值乘法
            ans = matrixMultiply(ans, baseMatrix);
        }
        // 进行矩阵乘法运算求矩阵频发 相当于整数幂的时候数值乘法 求数值的平方
        baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
    }
    return ans;
}

以上就是本文对于求解斐波拉契数列的各种办法，残缺代码如下：

public class Fibonacci {public static int fibonacci1(int n) {if (n <= 1)
      return n;
    return fibonacci1(n - 1) + fibonacci1(n - 2);
  }

  public static int fibonacci2(int n) {if (n <= 1)
      return n;
    int[] fib = new int[n + 1];
    // 进行初始化操作
    fib[0] = 0;
    fib[1] = 1;
    // 从前往后遍历失去 fib 数组的后果
    for (int i = 2; i <= n; i++) {fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
  }

  public static int fibonacci3(int n) {if (n <= 1)
      return n;
    // 进行初始化操作
    int a = 0;
    int b = 1;
    int fib = 0;
    // 从前往后遍历失去 fib 的后果
    for (int i = 2; i <= n; i++) {
      fib = a + b;
      a = b;
      b = fib;
    }
    return fib;
  }

  /**
   * 这个函数的目标是求解 base 的 n 次方
   * @param base
   * @param n
   * @return
   */
  public static int power(int base, int n) {if (n == 0) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 这个右移的目标是查看 n 对应的地位上是否为 1 如果为 1 就须要进行乘法运算
      // 这就相当于 ans *= base^i
      if (((n >> i) & 1) == 1) {ans *= base;}
      // base 的变动状况为 base^1 base^2 base^3 ...
      // 比如说当 base 为 2 时，base 的变动状况为 1, 2, 4, 8, 16, 32, 64, ...
      base *= base;
    }
    return ans;
  }

  public static int pow(int base, int n) {
    int ans = 1;
    for (int i = 0; i < n; i++)
      ans *= base;
    return ans;
  }

  /**
   * 这里为了简略期间，因为咱们的矩阵乘法是 2x2 的
   * 所以能够间接做这样的简略的乘法
   * @param a
   * @param b
   * @return
   */
  public static int[][] matrixMultiply(int[][] a, int[][] b) {int[][] ans = new int[2][2];
    ans[0][0] = b[0][0] * a[0][0] + b[0][1] * a[1][0];
    ans[0][1] = b[0][0] * a[0][1] + b[0][1] * a[1][1];
    ans[1][0] = b[1][0] * a[0][0] + b[1][1] * a[1][0];
    ans[1][1] = b[1][0] * a[0][1] + b[1][1] * a[1][1];
    return ans;
  }

  public static int[][] fibMatrixPower(int n) {int[][] baseMatrix = {{1, 1}, {1, 0}};
    if (n == 1)
      return baseMatrix;
    // 初始化为单位矩阵 如果是整数幂 初始化为 1
    int[][] ans = {{1, 0}, {0, 1}};

    for (int i = 0; i < n; i++) {
      // 这个右移的目标是查看 n 对应的地位上是否为 1 如果为 1 就须要进行矩阵乘法运算
      if (((n >> i) & 1) == 1) {ans = matrixMultiply(ans, baseMatrix);
      }

      baseMatrix = matrixMultiply(baseMatrix, baseMatrix);
    }

    return ans;
  }

  public static int fibonacci(int n) {if (n <= 1) return n;
    int[][] mm = fibMatrixPower(n);
    return mm[1][0];
  }

  public static void main(String[] args) {System.out.println(fibonacci1(1));
//    System.out.println(power(2, 8));
//    System.out.println(power(2, 8));
    System.out.println(fibonacci(1));
  }
}

咱们从斐波拉契数列失去了什么

咱们当初来从新捋一下咱们在下面学习斐波拉契数列的思路：

首先咱们用于解决斐波拉契数列的办法是 递归法 然而这个办法有一个很大的问题，就是计算某个斐波拉契数的时候它依赖于它后面的斐波拉契数（这个过程相当于将一个大问题划分成若干个小问题），这个依赖会导致咱们进行很多反复的运算，为了解决这个问题咱们用到了 数组法，这其实就是一个用空间换工夫的办法，用数组将后面计算你的后果存储下来，防止反复计算。

通过剖析咱们公式，咱们发现咱们的数据依赖关系，咱们在计算某个斐波拉契数的时候只须要依赖它后面的两个斐波拉契数，因而咱们不必存储咱们计算的每一个斐波拉契数，只须要保留两个值即可，这就是咱们 优化数组法 的原理。

最初咱们通过 疾速矩阵幂 的办法将咱们的工夫复杂度从 O(n) 升高到了O(long(n))，这个办法其实带有肯定的技巧性，在大多数动静布局的算法当中咱们用不到它，也就是说它的普适性并不强。

从下面的剖析咱们能够总结咱们在应用动静布局时的大抵思路：

  • 将大问题划分成小问题，小问题持续划分 ……，学术一点的话说就是重叠子问题。
  • 是否存在反复计算，如果存在应用空间换工夫的办法进行优化，这是动静布局一个十分重要的点。
  • 是否可能对数组的空间复杂度进行优化。

01 背包问题

背包问题：有 $N$ 件物品和一个可能接受分量为 $V$ 的背包。每件物品只能应用一次。第 $i$ 件物品的价值是 $v_i$，分量是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包可能接受的分量，且总价值最大。

比方上面的 4 个物品，背包可能接受的最大分量为 5，咱们应该如何抉择，使得咱们取得的总价值最大：

物品 分量 价值
A 1 2
B 2 4
C 3 4
D 4 5

这个问题还是比较简单，咱们间接看就晓得抉择物品 B 和物品 C 失去的价值最大。那么咱们如何设计一个算法去实现这个问题呢？首先对于每一个物品都有两种状况，抉择和不抉择，咱们须要抉择两种状况当中可能获取最大价值的那种状况。

抉择或者不抉择

在动静布局当中咱们通常通过数组进行求解，在 01 背包问题当中，咱们设置一个数组 dp[i][j]，示意当咱们只应用前i 个物品（物品编号从 0 开始，第一个物品的下标为 0）且以后残余可能接受的分量为 j 时，可能获取的最大的价值，那么咱们要求解的值为 dp[N - 1][V]，物品下标从0 开始。

比如说：dp[2][3]示意在本题当中的四个物品 A,B,C,D 当中只抉择后面两个物品A,B，且背包还可能接受3de 分量。

依据下面的剖析咱们能够失去上面一个动静布局公式：

dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])，其中 w 和v别离示意第 i 个物品的分量和价值。

你真的了解了背包问题 for 循环的程序吗

咱们曾经失去了咱们的动静转移公式dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])，咱们当初了来好好剖析这个公式：

咱们能够很分明的看到要想求解 dp[i][j] 的值，咱们首先须要晓得 dp[i - 1][j - w] 和dp[i - 1][j]的值，他们之间的依赖关系能够用下图来示意。

咱们在求解 dp[i][j] 的值的时候，首先的需要求出它依赖的数据，当咱们在求解第动静布局数组 dp 的第 i 行时，咱们首先需要求出第 i - 1 行的值。然而咱们在求第 0 行的时候并没有 -1 行，因而咱们首先须要进行初始化。dp[i][j]的含意是只应用前 i 个物品且接受分量只有 j 时，咱们能过获取的最大的价值！！！

那么初始化 dp[0][j] 的含意就是当咱们只有第 1 个物品可抉择而且背包可能接受的分量为 j 时可能获取的最大的价值，那么咱们很容易进行初始化（当 j 大于等于物品的分量的时候能够获取第一个物品的价值，否则获取价值为 0，因为只有一个物品，然而背包接受不了它的分量）：

Java 代码实现动静布局：

import java.util.Scanner;

public class Main {public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[][] dp = new int[N][V + 1];

    // 咱们一共有 N 个物品，背包可能接受的分量为 V
    // dp 数组就是咱们下面提到的动静布局的数组
    // w[i] 就是第 i 个物品的分量
    // v[i] 就是第 i 个物品的价值
    // 进行数组的初始化
    for (int i = w[0]; i < V; ++i) {dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= w[i]) // 只有可能接受物品的分量能力进行抉择
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        else
          dp[i][j] = dp[i - 1][j];
      }
    }
    // 返回可能取得的最大的价值
    // 这个式子表明前 N - 1 个可抉择且咱们的背包接受分量为 V 时最大收益
    return dp[N - 1][V];
  }


  public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    for (int i = 0; i < N; i++) {w[i] = scanner.nextInt();
      v[i] = scanner.nextInt();}
    System.out.println(backpack(w, v, V));
  }
}

C++ 代码实现动静布局

#include <iostream>
using namespace std;

#define LENTGH 1005
int N, V;
int v[LENTGH];
int w[LENTGH];
int dp[LENTGH][LENTGH];

int backpack() {
    // 咱们一共有 N 个物品，背包可能接受的分量为 V
    // dp 数组就是咱们下面提到的动静布局的数组
    // w[i] 就是第 i 个物品的分量
    // v[i] 就是第 i 个物品的价值
    // 进行数组的初始化
    for (int i = w[0]; i < V; ++i) {dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= w[i]) // 只有可能接受物品的分量能力进行抉择
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    // 返回可能取得的最大的价值
    // 这个式子表明前 N - 1 个可抉择且咱们的背包接受分量为 V 时最大收益
    return dp[N - 1][V];
}

int main() {
    cin >> N >> V;
    for (int i = 0; i < N; ++i) {cin >> w[i] >> v[i];
    }
    cout << backpack();
    return 0;
}

咱们在上述两份代码当中的 for 循环程序是遍历所有的物品，而后背包容量从 0 变动到 V，那么咱们背包容量变动能不能从V 变动到 0 呢？答案是能够的：

从上图看咱们在计算第 i 的数据的时候咱们只依赖第 i - 1 行，咱们在第 i 行从后往前遍历并不会毁坏动静转移公式的要求。

上面的代码同样能够是正确的：

public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[][] dp = new int[N][V + 1];

    // 咱们一共有 N 个物品，背包可能接受的分量为 V
    // dp 数组就是咱们下面提到的动静布局的数组
    // w[i] 就是第 i 个物品的分量
    // v[i] 就是第 i 个物品的价值
    // 进行数组的初始化
    for (int i = w[0]; i < V; ++i) {dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = V; j >= 0; --j) {if (j >= w[i]) // 只有可能接受物品的分量能力进行抉择
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    // 返回可能取得的最大的价值
    // 这个式子表明前 N - 1 个
    return dp[N - 1][V];
}

背包问题的空间优化——滚动数组

咱们在解决背包问的时候咱们是开拓了一个二维数组 dp，那么咱们能不能想斐波拉契数列那样升高算法的空间复杂度呢？咱们曾经很分明了咱们在计算dp 数据的时候进行计算的时候只应用了两行数据，那么咱们只须要申请两行的空间即可，不须要申请那么大的数组空间，计算的时候重复在两行数据当中交替计算既可。比如说咱们曾经计算好第一行的数据了（初始化），那么咱们能够依据第一行失去的后果失去第二行，而后依据第二行，将计算的结后果从新存储到第一行，如此交替重复，像这种办法叫做 滚动数组。

  public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[][] dp = new int[2][V + 1];

    // 咱们一共有 N 个物品，背包可能接受的分量为 V
    // dp 数组就是咱们下面提到的动静布局的数组
    // w[i] 就是第 i 个物品的分量
    // v[i] 就是第 i 个物品的价值
    // 进行数组的初始化
    for (int i = w[0]; i < V; ++i) {dp[0][i] = v[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = V; j >= 0; --j) {if (j >= w[i]) // 只有可能接受物品的分量能力进行抉择
          dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j],
              dp[(i - 1) % 2][j - w[i]] + v[i]);
        else
          dp[i % 2][j] = dp[(i - 1) % 2][j];
      }
    }
    // 返回可能取得的最大的价值
    // 这个式子表明前 N - 1 个
    return dp[(N - 1) % 2][V];
  }

背包空间再优化——单行数组和它的遍历程序问题

咱们还能持续压缩空间吗🤣？咱们在进行空间问题的优化的时候只有不毁坏动静转移公式，只须要咱们进行的优化可能满足 dp[i][j] 的计算在它所依赖的数据之后计算即可。

public static int backpack(int[] w, int[] v, int V) {
    int N = w.length;
    int[] dp = new int[V + 1];
    // 咱们一共有 N 个物品，背包可能接受的分量为 V
    // dp 数组就是咱们下面提到的动静布局的数组
    // w[i] 就是第 i 个物品的分量
    // v[i] 就是第 i 个物品的价值
    // 进行数组的初始化
    for (int i = w[0]; i < V; ++i) {dp[i] = v[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = V; j >= w[i]; --j) {dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]);
        }
    }
    return dp[V];
}

咱们当初来好好剖析一下下面的代码：

  • 依据动静转移公式 dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j]) 咱们晓得，第 i 行的数据只依赖第 i - 1 行的前 j 个数据，跟第 j 个数据之后的数据没有关系。因而咱们在应用一维数组的时候能够从后往前计算（且只能从后往前计算，如果从前往后计算会破话动静转移公式，因为第 j 个数据跟他后面的数据有依赖关系，跟他前面的数据没有依赖关系）就可能满足咱们的动静转移公式。

  • 如果咱们从在应用单行数组的时候从前往后计算，那么会使得一维数据后面局部数据的状态从 i - 1 行的状态变成第 i 行的状态，像上面这样。

然而一维数组当中后局部的数据还是 i - 1 行的状态，当咱们去更新他们的时候他们依赖后面局部数据的 i - 1 行的状态，然而他们曾经更新到第 i 的状态了，因而毁坏了动静布局的转移方程，然而如果咱们从后往前进行遍历那么后面的状态始终是第 i - 1 行的状态，因而没有毁坏动静布局的转移方程，因而咱们须要从后往前遍历。

动静布局总结

动静布局的套路

通过仔细分析下面两个算法题，咱们能够失去上面的一些心得：

  • 动静布局有着工夫换空间的特点，这样能够升高算法的工夫复杂度。
  • 动静布局个别都有重叠子问题，咱们须要剖析重叠子问题，失去动静转移方程，比方在斐波拉契数列当中的转移方程为f(i) = f(i - 1) + f(2)，背包问题的动静转移方程为dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])。
  • 失去转移方程之后，咱们须要进行数组的初始化，比方在斐波拉契数列当中咱们须要初始化下标为 0 和1的数据，在背包问题当中咱们要初始化第一行的数据。
  • 依据下面失去的信息进行 for 循环操作，运算失去最终的后果。
  • 剖析是否可能优化空间复杂度。

动静布局为什么叫动静布局

学习完以上两个问题之后咱们能够通过动静布局的特点去找到这个答案。首先咱们须要明确什么是 布局 所谓的 布局 就是寻找最优值的过程，比如说咱们在旅行的时候做布局就是为了又更好旅行体验，而咱们在做算法题的时候须要找到最好的后果，比方在背包问题当中咱们要找到价值最大的一种抉择，这也是一种布局，那为什么是动静的呢？所谓动静就是咱们在寻找最优值的过程当中，抉择是变动的。比如说对于背包问题的公式 dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j]) 咱们在计算出后果之前并不知道那种抉择好，因为咱们要抉择两者两头值较大的哪个抉择，这就是动静抉择的过程！！！

以上就是本篇文章的所有内容了，心愿大家有所播种，我是 LeHung，咱们下期再见！！！

更多内容在我的项目 https://github.com/Chang-LeHu…!!!

关注公众号：一无是处的钻研僧，理解更多计算机常识。

退出移动版