简介

动静布局（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中应用的，通过把原问题合成为绝对简略的子问题的形式求解简单问题的办法。

斐波那契数列

学习动静布局之前，咱们先理解一下斐波那契数列是什么。

斐波那契数列又译为 费波拿契数 、 斐波那契数列 、 费氏数列 、 黄金分割数列。

用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是：

0,1,1,2,3,5,8,13,21,34,55,89 ...

fib(n) = fib(n - 1) + fib(n - 2);

从中咱们能够发现从第三个数开始的值是前两个值的和。

假如我在如下图中失去 fib(7)的斐波那契数列，咱们能够晓得想取得 7 的斐波那契数列的话 7 就要获取 fib(6) + fib(5) 的值，但 fib(6) 又须要获取 fib(5) + fib(4)… 咱们会发现有很多反复的计算，导致工夫复杂度为O(2n)

咱们发现左侧曾经进行过 fib(5)的计算，右侧又有一个 fib(5)，其实咱们齐全能够在左侧计算 fib(5)的时候将值保存起来，这样咱们在右侧间接应用这个值就能够了。

如果咱们想算 fib(6)的话，首先咱们晓得 1 和 2 都等于 1, 顺次相加得出如下：

数组        1 2 3 4 5 6
斐波那契数   1 1 2 3 5 8

咱们从递归改为递推的话，工夫复杂度就会变成O(n)。

咱们先用两个经典的问题来引出动静布局算法。

最优打工问题

如上图，咱们一共有八个工作能够进行打工，对应的红色数字就是打工所赚取的钱，长度就是工夫，在同一时间只能做一个工作，咱们如何赚取最多的钱？

其实在面临一个抉择的时候，只有两个抉择，选 or 不选

咱们须要找到一个最优解，如果抉择 opt(8)咱们看看有什么后果。

图中咱们能够看进去，咱们抉择第 8 号工作的话，咱们能够赚取 4 块钱，然而咱们就无奈再做 6、7 号工作了，咱们只思考工夫紧挨着的工作的最优解，咱们就能够在前 5 个中再选取最优解即可。

如果咱们不选，很简略，只有从前 7 个中获取最优解 opt(7)。

而后咱们就要在选和不选中抉择赚钱最多的那个就 ok 了。

再举个例子，如果要做第 7 号工作，4、5、6、8 都不能做，咱们能够看到紧挨着的只有 3 号工作所以代码就是：prev(7) = 3。

咱们看一下 prev 函数是怎么计算出来的。

如果咱们要做 1 号工作，因为咱们只思考后面的所以如果要做 1 号工作的话，咱们后面就没有工作能够做，所以就是 0，以此类推我间接把表格列出来

| i | prev(i) |
| — | — |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
| 4 | 1 |
| 5 | 0 |
| 6 | 2 |
| 7 | 3 |
| 8 | 5 |

开展的树图如下：

咱们在图中发现呈现了咱们之前所说的重叠的问题。

咱们须要做的就是保留曾经开展过的值，缩小不必要的屡次开展的问题，通过数组来保留曾经有过的值。

| 工作编号 | 之前可做工作编号 | 当前任务最大收益 | 做 | 不做 | 所选工作 |
| — | — | — | — | — | — |
| i | prev(i) | opt(i) | opt(i) + opt(prev(i)) | opt(i-1) |[i] |
| 1 | 0 | 5 | 5 | 0 | [1] |
| 2 | 0 | 5 | 1 | 5 | [1] |
| 3 | 0 | 8 | 8 | 5 | [3] |
| 4 | 1 | 9 | 9 | 8 | [1,4] |
| 5 | 0 | 9 | 6 | 9 | [1,4] |
| 6 | 2 | 9 | 4 | 9 | [1,4] |
| 7 | 3 | 10 | 10 | 9 | [3,7] |
| 8 | 5 | 13 | 13 | 10 | [1,4,8] |

这样咱们就能够很容易的到最大收益的工作编号。

背包问题

题目：当初有四个物品，背包总容量为 8，背包最多能装下价值为多少的物品？

咱们用一个表格来展现咱们的背包数据。

** 咱们第一行示意背包容量，第一列示意物品的编号。**

每个格子示意在以后背包容量的状况下，思考前 n 个物品的最佳组合，所能装入的最大价值为多少，就填入方框中。

首先咱们开始填入背包编号和容量，第一行全副是 0，因为第一行示意前 0 个物品的最佳组合，也就是没有物品，所以咱们不须要管背包容量有如许大，咱们没有物品，所以都是 0。

第一列也全副是 0，因为咱们对应的背包容量是 0，所以不论有多少物品，咱们没有容量，所以都是 0。

咱们持续往右填，物品编号为 1，背包容量为 1，咱们思考前 1 个物品在容量为 1 的状况下，所能装入的最大价值为多少。

在每次装入之前咱们须要思考以后物品是否能装入背包

通过咱们的已知条件，咱们晓得物品编号为 1 的物品它的体积为 2。他比咱们的背包容量还要大，所以咱们只有一个抉择，就是不装入 1 号物品。所以咱们填入 0。

咱们持续往右填，物品编号为 1，背包容量为 2，咱们的物品体积为 2，当初咱们就面临两个抉择，装？or 不装？

咱们一步步剖析，如果咱们抉择不装，那咱们就和前 0 号物品所对应最大价值是一样的，也就是 0。

如果咱们抉择装入 1 号物品，物品编号为 1，背包容量为 2，物品的体积也是 2，物品的价值为 3。咱们装入后背包容量 2-2=0，这时候咱们的价值为 3。

由此咱们能够晓得，装 = 价值为 3 or 不装 = 价值为 0，这时候咱们选取最大的那个，也就是装。咱们填入值为 3。（后续填法统一，就不过多赘述）

咱们持续填，当初来到物品编号为 2，背包容量为 3 这个地位，咱们发现物品编号为 2 的体积为 3，装入后背包容量 3-3=0，这时候咱们的价值为 4。所以咱们当初又来到了 装 or 不装 问题，装的话就是 4，不装的话就选取前 n 个物品在此背包的最大价值也就是 3，4>3 所以咱们抉择装入。

当咱们依照此办法以此类推咱们能够失去如下表格：

总结：

1. 如果装不下以后物品，那么前 n 个物品的最佳组合和前 n - 1 个物品的最佳组合是一样的。
2. 如果装得下以后物品则有两种状况：

   假如 1：装入以后物品，在给以后物品预留了相应空间的状况下，前 n - 1 个物品的最佳组合加上以后物品的价值就是总价值。

   假如 2：不装以后物品，那么前 n 个物品的最佳价值组合，和前 n - 1 个物品的最佳价值组合是一样的。

   而后咱们选取假如 1 和假如 2 中较大的价值，为以后组合的最大价值。

背包问题回溯

问题进阶：在背包内总价值最大的状况下，背包内装了哪些物品呢？

咱们晓得背包内最大总价值为 10，咱们须要查看以后物品编号为 4 是否放入了背包，进行 n - 1 咱们发现物品编号为 3 容量为 8 时价值为 9，9 != 10 由此能够晓得物品编号 4 确实放入了背包，物品编号 4 对应的体积为 5，咱们找到 n - 1 也就是物品编号为 3 且背包容量 8 -5= 3 的地位，如下图：

首先须要晓得以后物品有没有放进去，进行 n - 1 发现最大价值是一样的，所以能够晓得以后物品没有放进去，进行往上挪动，来到背包 2 的地位，咱们还是须要晓得以后物品有没有放进去，进行 n - 1 发现最大价值为 3 以后最大价值为 4，所以晓得物品 2 放入了背包。

而后咱们进行以后容量减去物品 2 的容量就是 3 -3=0，找到物品编号为 1，背包容量为 0 的地位进行判断。而背包容量为 0 必定没有放任何货色，所以持续回溯就到了物品编号为 0，背包容量为 0，回溯完结。

题目练习

当初有这么一道题 数组如下：

arr[1,2,4,1,7,8,3]

咱们在抉择某个数的时候不能抉择相邻的两个数，抉择 1 就不能抉择 2，抉择 7 就不能抉择 1 和 8，如何得出抉择的是最大的和呢？

假如咱们抉择下标为 6 的，arr[6]会是怎么的呢？我把流程画进去。

这个时候很显著，咱们又遇见了之前说的重叠问题。

间接上代码

第一种递归写法（不举荐）

    public static void main(String[] args) {int[] arr = new int[]{1, 2, 4, 1, 7, 8, 3};
        System.out.println(resOpt(arr, 6));
    }

    private static int resOpt(int[] arr, int i) {if (i == 0) {return arr[0];
        } else if (i == 1) {return Math.max(arr[1], arr[0]);
        } else {int case1 = resOpt(arr, i - 2) + arr[i];
            int case2 = resOpt(arr, i - 1);
            return Math.max(case1, case2);
        }
    }

后果为：15

然而这种写法有个很重大的问题，就是咱们没有思考重叠的问题！效率非常低，工夫复杂度为O(2n)。

第二种：动静布局

    public static void main(String[] args) {int[] arr = new int[]{1,2,4,1,7,8,3};
        System.out.println(dpOpt(arr));
    }

    private static int dpOpt(int[] arr) {int[] opt = new int[arr.length];
        opt[0] = arr[0];
        opt[1] = Math.max(arr[1], arr[0]);
        for (int i = 2; i < arr.length; i++) {int case1 = opt[i - 2] + arr[i];
            int case2 = opt[i - 1];
            opt[i] = Math.max(case1, case2);
        }
        return opt[opt.length - 1];
    }

题目练习

给定一个整数数组 arr 和一个目标值 target，请是否有一组数字加起来等于 target，找到返回 true，未找到返回 false。

给定 arr = [3,34,4,12,5,2], target = 9

因为 nums[2] + nums[5] = 4 + 5 = 9
所以返回 true

如果咱们先抉择了 arr[5]，咱们还是面临两种状况，选 or 不选。

抉择了 arr[5] 也就是之前要有数组加起来是 7，7+2=9，如果不选，也就是 arr[4]之前要等于 9。

具体还是和背包问题一样，填入表格即可。最终获取最右下角的值，就是是否有匹配到的后果。

    public static void main(String[] args) {int[] arr = {3, 34, 4, 12, 5, 2};
        System.out.println(dpSubSet(arr, 9));
    }

    public static boolean dpSubSet(int[] arr, int target) {boolean[][] dp = new boolean[arr.length + 1][target + 1];
        for (int k = 1; k <= target; k++) {
            // 为第一行赋初值
            dp[0][k] = false;
        }
        for (int k = 1; k <= arr.length; k++) {
            // 为第一列赋初值
            dp[k][0] = true;
        }
        dp[0][0] = true;

        for (int i = 1; i <= arr.length; i++) {for (int j = 1; j <= target; j++) {if (arr[i - 1] > j) {dp[i][j] = dp[i - 1][j];
                } else {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }
        return dp[arr.length][target];
    }

后果：true