题目描述 有 n 件物品，每件物品有一个重量和一个价值，分别记为 w1，w2，…，wn 和 c1，c2，…，cn。现在有一个背包，其容量为 wk，要从 n 件物品种任取若干件。要求：（1）重量之和小于或等于 wk；（2）价值之和最大。 输入： 共 3 行，第一行 2 个整数，表示 n 和 wk；第二行 n 个整数表示每一个物品的重量，第三行 n 个整数表示每一个物品的价值。 输出： 一行一个整数，表示符合背包容量的最大价值。 样例： 8 200 79 58 86 11 28 62 15 68 83 14 54 79 72 52 48 62 暴力枚举 我们以只有 A、B、C 三件物品的情况为例，对于每一个物品都存在拿和不拿两种情况。以0表示不拿当前物品，以1表示拿当前物品，可以有如下分析结果。 可能上面的图看起来不够清晰，我们从左至右逐一列举出来观察，一眼就可以看出来规律。其实就是十进制的 0、1、2、3、4、......可枚举的最大值即 2n-1。 000 001 010 011 100 101 110 111 根据上面的分析，我们可以写出如下代码。 #include<bits/stdc++.h> using namespace std; int main() { int n, wk; int w[10000], c[10000]; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } int ans = 0; int max_val = 1 << n; // 逐一枚举 for(int i = 0; i < max_val; i++){ int ww = 0, cc = 0; int index = 0; // 转二进制 int cur = i; while(cur){ int bit = cur % 2; // 若拿第 index 个物品，则累加其重量和价值 if(bit){ ww += w[index]; cc += c[index]; } cur = cur >> 1; index++; } //计算最大值 if(ww <= wk && ans < cc){ ans = cc; } } //输出最大值 cout<<ans<<endl; } 递归求解 我们把背包容量为wk，有n个物品可以选择的问题表示为slove(wk, n)。那么在背包剩余容量可以装下第 n 个物品时，该问题可以表示为求如下两个问题的最大值 选第 n 个物品：c[n-1] + slove(wk-w[n-1], n-1) 不选第 n 个物品：slove(wk, n-1) 在背包剩余容量无法装下第 n 个物品时，问题直接变为 不选第 n 个物品：slove(wk, n-1) 可以发现上述三个子问题可以继续向下拆分为规模更小，但类型一致的子子问题。于是可以写出如下递归求解代码。 #include<bits/stdc++.h> using namespace std; int w[30]={0}, c[30]={0}; // wk 背包剩余重量 // ch 可选项 int slove(int wk, int ch) { if(wk <= 0 || ch <= 0){ return 0; } // 若背包剩余容量无法装下 w[ch-1]，则直接丢弃第 ch 个物品 if(w[ch-1] > wk){ return slove(wk, ch-1); } // 若背包剩余容量能装下 w[ch-1]，则计算装和不装的最大值 int a = c[ch-1] + slove(wk-w[ch-1],ch-1); int b = slove(wk, ch-1); return a > b ? a : b; } int main() { int n, wk; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } cout<<slove(wk, n); } 动态规划 递归在执行过程中会存在重复计算相同子问题的情况，我们可以将其改为用循环实现，即动态规划的写法。dp[i][j]的含义即为：在背包容量为i，可选物品数量为j的情况下，符合背包容量的最大值。具体代码如下所示： #include<bits/stdc++.h> using namespace std; int w[30]={0}, c[30]={0}; int main() { int n, wk; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } int dp[1000001][21] = { 0 }; for(int i = 1; i <= wk; i++) { for(int j = 1; j <= n; j++) { // 若背包剩余容量无法装下 w[j-1]，则直接丢弃第 j 个物品 if(w[j-1] > i) { dp[i][j] = dp[i][j-1]; } else { // 若背包剩余容量能装下 w[j-1]，则计算装和不装的最大值 int a = c[j-1] + dp[i-w[j-1]][j-1]; int b = dp[i][j-1]; dp[i][j] = a > b ? a : b; } } } cout<<dp[wk][n]; }

原写了 Java 版本的如何求解换钱的方法数，近期进行了一些细节上的补充，以及部分错误更正，将语言换为了 C++ 语言。 基础题目 假设你现在拥有不限量的 1 元、5 元、10 元面值纸币，路人甲希望找你换一些零钱，路人甲拿出的是一张 100 元面值的纸币，试求总共有多少种换零钱的方法？ 分析：因为总共只有 3 种面值小额纸币，所以将所有可能进行枚举，直接暴力解决即可。 #include<bits/stdc++.h> using namespace std; int slove() { int ans = 0; // 10 元张数 for(int i = 0; i <= 10; i++) { // 5 元张数 for(int j = 0; j <= 20; j++) { // 1 元张数 for(int k = 0; k <= 100; k++) { int cur = i*10 + j*5 + k*1; if(cur == 100) { ans++; } } } } return ans; } int main() { cout<<slove(); } 递归求解 基础题目中是拥有固定种类的小额纸币，即使再多几种小额纸币也没关系，大不了在嵌套几个循环就能解决。现在需要将题目的难度加大一点，改为小额纸币的种类和需要换零钱的总额由用户输入，即小额纸币种类和总额都不在固定，那么如何解决？ 输入共有三行： 第一行：小额纸币种类数量 第二行：不同小额纸币的面值 第三行：需要换零钱的总额 分析：虽然现在种类和总额都是变量了，但是上文中的基础版本还是被包含在此问题中，所以我们还是以上文中的 1 元、5 元、10 元换 100 元进行分析，找一找除了枚举是否还有其他方法解决。 我们先固定一种零钱的数量，剩下的钱用剩余零钱去兑换，即： 用 0 张 1 元换，剩下的用 5、10 元换，最终方法数为 count0； 用 1 张 1 元换，剩下的用 5、10 元换，最终方法数为 count1； ...... 用 100 张 1 元换，剩下的用 5、10 元换，最终方法数为 count100； 那么最终换钱的方法综述即为count0 + count1 + count2 + ... + count100。 上面的分析中，我们把原来的大问题拆为了 101 个小问题，且每一个小问题都有很相似的地方，即： 求用 5、10 元换 100 元的方法数 求用 5、10 元换 95 元的方法数 ...... 求用 5、10 元换 0 元的方法数 如果我们对这 101 个小问题再进行同样思路的分析，即再固定 5 元零钱的数量，那么就能把问题划分成了规模更小，但问题类型一样的小小问题。即递归的思路，可以写出如下代码。 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度，即：小额纸币种类 // index 表示上文分析中的当前固定第几张 // target 表示现在要兑换的钱的总额 int slove(int index, int target) { int ans = 0; if(index == len) { ans = target == 0 ? 1 : 0; } else { for(int i = 0; i*money[index] <= target; i++) { // 剩余待换零钱的总额 int cur_total = target-(i * money[index]); ans = ans + slove(index+1, cur_total); } } return ans; } int main() { int target; cin>>len; // 零钱种类 for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; // 兑换总额 cout<<slove(0, target); } 优化递归 可以发现上文所写的递归代码存在大量的重复过程，比如下面两种情况，后面所求的子问题是完全一样的，导致程序运行时间的浪费。 已经使用了 5 张 1 元、0 张 5 元，剩下的 95 元用 5 元和 10 元兑换 已经使用了 0 张 1 元、1 张 5 元，剩下的 95 元用 5 元 和 10 元兑换 既然前面已经求解过相同的子问题了，那么我们是否可以在第一次求解的时候，将计算结果保存下来，这样下次遇到相同子问题的实际，直接查出来用就可以，省去再次求解的时间。 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度，即：小额纸币种类 // 用于存储子问题的解 int val_map[1000][1000] = { 0 }; // 0 表示该子问题没有算过 // -1 表示算过，但该子问题无解 // 其它值，即此子问题的方法数 int slove(int index, int target) { int ans = 0; if(index == len) { ans = target == 0 ? 1 : 0; } else { for(int i = 0; i*money[index] <= target; i++) { // 剩余待换零钱的总额 int cur_total = target-(i * money[index]); int pre_val = val_map[index+1][cur_total]; // 如果 val 为 0，说明该子问题没有被计算过 if(pre_val == 0) { ans = ans + slove(index+1, cur_total); } else { ans += pre_val == -1 ? 0 : pre_val; } } } // 存储计算结果 val_map[index][target] = ans == 0 ? -1 : ans; return ans; } int main() { int target; // 零钱种类 cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(0, target); } 动态规划 上面对递归的优化方案已经能看出来动态规划的影子了，沿着前文先计算再查表的思路继续思考，我们能否提前把所有子问题都计算出答案，对每个子问题都进行查表解决。也即将最初的递归方案改为循环的实现。 所有的递归都能改为循环实现 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度，即：小额纸币种类 // 用于存储子问题的解 // val_map[i][j] 表示用 money[0...i] 的小面额零钱组成 j 元的方法数 int val_map[1000][1000] = { 0 }; int slove(int target) { // 第一列表示组成 0 元的方法数，所以为 1 for (int i = 0; i < len; i++) { val_map[i][0] = 1; } // 第一行表示只使用 money[0] 一种钱币兑换钱数为i的方法数 // 所以是 money[0] 的倍数的位置为 1，否则为 0 for (int i = 1; money[0]*i <= target; i++) { val_map[0][money[0]*i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { for (int k = 0; j >= money[i]*k; k++) { /* val_map[i][j] 的值为： 用 money[0...i-1] 的零钱组成 j 减去 money[i] 的倍数的方法数 因为相比 val_map[i-1][j]，只是多了一种零钱的可选项 */ val_map[i][j] += val_map[i-1][j-money[i]*k]; } } } return val_map[len-1][target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); } 动归优化 在上文第一版动态规划代码的优化中已经能发现，其实val_map[i][j]的值由两部分组成，分别为： 用 money[0...i-1] 的零钱组成换 j 元的方法数 用 money[0...i-1] 的零钱换 j-money[i]*k（k=1,1,2,3....）元的方法数之和 对于第二种情况来说，其累加值实际上就是val_map[i][j-money[i]]，即用money[0...i]的零钱换 j-money[i]元的方法数。至于具体为什么累加值与val_map[i][j-money[i]]相等，我们可以借助递归方法时的分析方式进行理解。 用 money[0...i-1] 的零钱组成换 j 元的方法数对应： 用 0 张 money[i] 换，剩下的用 money[0...i-1] 换 用 money[0...i-1] 的零钱换 j-money[i]*k（k=1,1,2,3....）元的方法数之和对应： 用 1 张 money[i] 换，剩下的用 money[0...i-1] 换 用 2 张 money[i] 换，剩下的用 money[0...i-1] 换 ...... 所以第二部分的值即为val_map[i][j-money[i]]。依据此处的分析，我们可以在原有基础上去掉第三层循环，减少程序运行所花费的时间。 #include<bits/stdc++.h> using namespace std; int money[1000]; int len; int val_map[1000][1000] = { 0 }; int slove(int target) { for (int i = 0; i < len; i++) { val_map[i][0] = 1; } for (int i = 1; money[0]*i <= target; i++) { val_map[0][money[0]*i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { val_map[i][j] = val_map[i-1][j]; // 此处需要比较 j 的大小，防止数组越界 // 注意条件时 >= ，否则少计算 j 刚好为 money[i] 的情况 if(j >= money[i]) { val_map[i][j] += val_map[i][j-money[i]]; } } } return val_map[len-1][target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); } 空间压缩 仔细观察能发现，每一次更新val_map[i][j]的值时，它只依赖于上一行和当前这一行前面的元素。对于我们所求解的问题来说，它仅要求我们给出最终的答案即可，那么前面存储中间结果的那些元素实际上就会空间的浪费，因此我们可以思考一下如何在空间上进行压缩。 实际上我们只需要定义一个一维的数组，采用一些技巧对该数组进行滚动更新，按照合适的方向去更新数组，同样可以达到上面使用二维数组的效果。 #include<bits/stdc++.h> using namespace std; int money[1000]; int len; int val_map[1000] = { 0 }; int slove(int target) { // 第一行，只用 money[0] 换零钱 // 所以只能换 money[0] 倍数的钱 for (int i = 0; money[0]*i <= target; i++) { val_map[money[0] * i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { if(j >= money[i]) { // 在进行下面一步前 val_map[j] 的值就已经是 val_map[i-1][j] 了 val_map[j] += val_map[j-money[i]]; } } } return val_map[target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); }

参考内容: OI题解 - A decorative fence[POJ 1037] poj1037（dP+排列计数） 本文首发于牛客网：题解 | #牛牛摆木棒# 题目 牛客网 NC632 牛牛摆木棒、POJ1037-A decorative fence（美丽的栅栏） 描述 有n个木棒，长度为1到n，给定了一个摆放规则。规则是这样的：对于第 i (2≤i≤n−1)(2 \leq i \leq n-1)(2≤i≤n−1) 个木棒 aia_iai​，(ai>ai−1(a_i > a_{i-1}(ai​>ai−1​ && ai>ai+1)a_i > a_{i+1})ai​>ai+1​) 或 (ai<ai−1(a_i < a_{i-1}(ai​<ai−1​ && ai<ai+1)a_i < a_{i+1})ai​<ai+1​)。求满足规则的从小到大的第k个排列是什么呢。 对于两个排列 s 和 t：如果存在 j 有任意 i<ji<ji<j 使得 si==tis_i == t_isi​==ti​ 且 sj<tjs_j < t_jsj​<tj​，视为排列 s 小于排列 t。 示例 输入：3,3 返回值：[2,3,1] 说明：第一小的排列为：[ 1 , 3 , 2 ] 第二小的排列为：[ 2 , 1 , 3 ] 第三小的排列为：[ 2 , 3 , 1 ] 第四小的排列为：[ 3 , 1 , 2 ] 所以答案为：[ 2 , 3 , 1 ] 备注 (1≤n≤20,1≤k≤(n−1)!)(1 \leq n \leq 20, 1 \leq k \leq (n-1)!)(1≤n≤20,1≤k≤(n−1)!) 题意 该问题让我们求：n 的字典序排列中第 k 个波浪形的排列。什么是波浪形排列呢？即对排列中任意一个数字（除开第一个和最后一个）aia_iai​，只能 aia_iai​ 比 ai−1a_{i-1}ai−1​ 和 ai+1a_{i+1}ai+1​ 都小或者都大。比如 2 1 3和1 3 2是波浪形排列，但1 2 3就不是波浪形排列。 DFS 枚举 最容易想到的解决方案是把 n 的所有排列按字典序列出来，然后再逐一检查是否是波浪形排列，直接取出第 k 个波浪形排列即可。 我们以 3 的全排列为例画出如下树形图，非常容易的就能发现只要对这棵树进行深度优先遍历，就能够按字典序得到所有排列。但并不是所有排列都满足波浪形这个条件，所以我们每得到一个排列都需要检查该排列是否为波浪形，直到检查到第 k 个排列为止，返回该排列即可。 class Solution { public: // 记录当前已经有多少个波浪形排列 long long count = 0; // 记录最后的结果 vector<int> res; /** * * @param n int整型 木棒的个数 * @param k long长整型 第k个排列 * @return int整型vector */ vector<int> stick(int n, long long k) { // 用于标记当前考虑的数字是否已经被选择 bool visited[25] = {false}; // 用于记录已经选了哪些数 vector<int> path; dfs(n, 0, path, visited, k); return res; } /** * * @param n 可选的数字范围 * @param deep 递归到第几层了 * @param path 已经选的数字 * @param visited 记录哪些数已经被选了 * @param k 是否已经到第 k 个波浪形排列了 */ void dfs(int n, int deep, vector<int> path, bool visited[], long long k) { // 递归层数和范围相等，说明所有的数字都考虑完了，因此得到一个排列 if(deep == n){ // 判断该排列是否为波浪形排列 bool flag = true; for(int i = 1; i < n-1; i++){ if((path[i] > path[i-1] && path[i] < path[i+1]) || (path[i] < path[i-1] && path[i] > path[i+1])){ flag = false; break; } } // 是波浪形排列，则统计一次 if(flag) { count++; } // 判断是否已经到第 k 个排列 if(count == k) { // 如果返回结果还没有被赋值，则将该排列赋值给 res // 因为我们使用的是递归，所以 count==k 会被满足多次 // 只有第一次满足时才是真正的 k 值，所以必须判断 res 是否为空 // 如果不判空，则程序记录的不是正确结果 if(res.empty()){ res = path; } // 到第 k 个波浪形排列了，递归返回 return ; } // 没有可以选择的数字了，回溯 return ; } // 还没有得出一个排列，则继续挑选数字组成排列 for(int i = 1; i <= n; i++) { // 如果该数字已经被选择了，则终止本次循环 if(visited[i]){ continue; } // 选中当前数字加入到排列中 path.push_back(i); visited[i] = true; // 下一次递归所传的值不变，只有递归层数需要 +1 dfs(n, deep+1, path, visited, k); // 回溯，需要撤销前面的操作 path.pop_back(); visited[i] = false; } } }; 在 C++ 的 algorithm 库中已经提供了一个全排列方法 next_permutation。按照STL文档的描述，next_permutation 函数将按字母表顺序生成给定序列的下一个较大的序列，直到整个序列为减序为止。因此我们可以偷个懒直接使用现有的函数。 class Solution { public: /** * * @param n int整型 木棒的个数 * @param k long长整型 第k个排列 * @return int整型vector */ vector<int> stick(int n, long long k) { vector<int> res; // 记录当前已经有多少个波浪形排列 long long count = 0; // 构造初始化排列 for(int i = 1; i <= n; i++) { res.push_back(i); } do { // 判断当前排列是否为波浪形排列 bool flag = true; for(int i = 1; i < n-1; i++) { if((res[i] > res[i-1] && res[i] < res[i+1]) || (res[i] < res[i-1] && res[i] > res[i+1])){ flag = false; break; } } if(flag) { count++; } if(count == k) { break; } } while (next_permutation(res.begin(), res.end())); return res; } }; 复杂度分析 我们来看一下这个深度优先遍历的时间复杂度分析，该算法的时间复杂度主要由递归树的结点个数决定。因为程序在叶子结点和非叶子结点的行为时不一样的，所以我们先计算非叶子结点的个数，我们一层一层的去计算它。 第 1 层因为只有一个空列表，所以我们不考虑它； 第 2 层表示的意思是从 n 个数中找出 1 个数，即 An1A_n^1An1​； 第 3 层表示的意思是从 n 个数中找出 2 个数，即 An2A_n^2An2​； 以此类推，全部非叶子结点的总数为： An1+An2+⋯AnnA_n^1 + A_n^2 + \cdots A_n^nAn1​+An2​+⋯Ann​ =n!(n−1)!+n!(n−2)!+⋯+n!= \frac{n!}{(n-1)!} + \frac{n!}{(n-2)!} + \cdots + n!=(n−1)!n!​+(n−2)!n!​+⋯+n! =n!(1(n−1)!+1(n−2)!+⋯+1)= n!\left(\frac{1}{(n-1)!} + \frac{1}{(n-2)!} + \cdots + 1\right)=n!((n−1)!1​+(n−2)!1​+⋯+1) ≤n!(1+12+14+⋯+12n−1)\leq n!\left(1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{n-1}}\right)≤n!(1+21​+41​+⋯+2n−11​) =n!×2（1−12n)= n! \times 2（1-\frac{1}{2^{n}})=n!×2（1−2n1​) <2n!< 2n!<2n! 每个非叶子结点都在内部循环了 n 次，所以非叶子结点的时间复杂度为 O(2n×n!)O(2n \times n!)O(2n×n!)，去除系数后得到 O(n×n!)O(n \times n!)O(n×n!) 。 最后一层叶子结点的个数就是 n!n!n! 个，但是我们对每个叶子结点都做了一次判断，因此叶子结点的时间复杂度依然是 O(n×n!)O(n \times n!)O(n×n!) 。 该问题的 k 控制了遍历的次数，最好情况即 O(n!)O(n!)O(n!)，最差即 O(n×n!)O(n \times n!)O(n×n!)，平均一下也不过只加了个系数，因此总的时间复杂度为 O(n×n!)O(n \times n!)O(n×n!)。 递归树的深度为 n，需要 O(n)O(n)O(n) 的空间；程序运行过程中保存了问题的最终答案，需要 O(n)O(n)O(n) 的空间，总共需要 O(2n)O(2n)O(2n) 的空间，因此该算法的空间复杂度为 O(n)O(n)O(n)。 动态规划 上述算法在运行过程中会超时，究其原因就是不论测试数据要求我们求第几个波浪形排列，我们都老老实实的从第一个开始数，当数据比较大时就会出现超时的情况。那么有没有办法能够减少一些不必要的过程呢？比如测试数据要求第 100 个波浪形排列，很明显前面 80 个排列肯定不满足情况，我们能否舍弃一部分搜索直接从第 80 个甚至第 90 个开始呢？ 我们先不考虑波浪形排列这个条件，如果是求第 k 个全排列的话是非常容易就能算出来的。还是以1 2 3的全排列为例，假设现在要求第 5 个全排列，可以发现只要第一个数确定了，排列数就由剩下数的排列方案决定，以1打头的排列有两个，以2打头的排列也有两个，而现在要求的是第 5 个排列，所以肯定不是以1或2打头的，这样我们就能直接跳过大部分不合法的排列，节省了时间。 仔细想想发现理想是比较丰满，上述方法的问题在于无法确定前面跳过的那部分里面究竟有多少个波浪形排列，因此这种直接计算的方法行不通。但是这个思想我们是可以借用一下的，那我们把一部分数据计算出来，尝试一下能不能找到规律。 当 n 为 1 时，总共有 1 个波浪形排列，1 打头的有 1 个； 当 n 为 2 时，总共有 2 个波浪形排列，1 打头的有 1 个； 当 n 为 3 时，总共有 4 个波浪形排列，1 打头的有 1 个； 当 n 为 4 时，总共有 10 个波浪形排列，1 打头的有 2 个； 当 n 为 5 时，总共有 32 个波浪形排列，1 打头的有 5 个； 当 n 为 6 时，总共有 122 个波浪形排列，1 打头的有 16 个； 列出来了 6 组数据都没有发现规律，这种方式基本得战略性放弃了。我们设置 A[i] 为 i 根木棒所组成的合法方案数，列数据找规律其实就是尝试找到 A[i] 和 A[i-1] 的规律，比如选定了某根木棒 x 作为第 1 根木棒的情况下，则剩下 i-1 根木棒的合法方案数为 A[i-1]。问题在于并不是这 A[i-1] 中每一种方案都能和 x 形成一种新的合法方案。 我们把第 1 根木棒比第 2 根木棒长的方案称为 W 方案，第 1 根木棒比第 2 根木棒短的方案称为 M 方案。A[i-1] 中方案中只有第 1 根木棒比 x 要长的 W 方案，以及第 1 根木棒比 x 要短的 M 方案，才能进行组合构成 A[i] 中的合法方案。 因此我们可以设A[i] = 0，先枚举 x，然后针对每一个 x 枚举它后面那根木棒 y，如果y > x（y < x同理）则有：A[i] = A[i] + 以 y 打头的 W 方案数，但是以 y 打头的 W 方案数，又和 y 的长短有关，因此只能继续将描述方式继续细化了。 设 B[i][k] 是 A[i] 中以第 k 短的木棒打头的方案数，则有： A[i]=∑k=1iB[i][k]A[i] = \sum_{k=1}^i B[i][k]A[i]=∑k=1i​B[i][k] B[i][k]=∑j=ki−1B[i−1][j](W)+∑n=1k−1B[i−1][n](M)B[i][k] = \sum_{j=k}^{i-1} B[i-1][j](W)+ \sum_{n=1}^{k-1} B[i-1][n](M)B[i][k]=∑j=ki−1​B[i−1][j](W)+∑n=1k−1​B[i−1][n](M) 公式中（W) 和 (M) 分别表示 W 方案和 M 方案，发现还是无法找出推导关系。设 C[i][k][0] 为 B[i][k] 中的 W 方案数，C[i][k][1] 为 B[i][k] 中的 M 方案数那么则有： B[i][k]=C[i][k][0]+C[i][k][1]B[i][k] = C[i][k][0] + C[i][k][1]B[i][k]=C[i][k][0]+C[i][k][1] C[i][k][1]=∑j=ki−1C[i−1][j][0]C[i][k][1] = \sum_{j=k}^{i-1} C[i-1][j][0]C[i][k][1]=∑j=ki−1​C[i−1][j][0] C[i][k][0]=∑n=1k−1C[i−1][n][1]C[i][k][0] = \sum_{n=1}^{k-1} C[i-1][n][1]C[i][k][0]=∑n=1k−1​C[i−1][n][1] 至此状态转移方程就出来了，初始条件为：C[1][1][0]=C[1][1][1] = 1，下面就可以开始写代码了。 class Solution { public: /** * * @param n int整型 木棒的个数 * @param k long长整型 第k个排列 * @return int整型vector */ vector<int> stick(int n, long long s) { long long dp[21][21][2]; memset(dp,0,sizeof(dp)); dp[1][1][0] = dp[1][1][1] = 1; for (int i = 2; i <= n; i++){ // 枚举第一根木棒的长度 for (int k = 1; k <= i; k++){ // W 方案枚举第二根木棒的长度 for (int m = k; m < i; m++){ dp[i][k][0] += dp[i-1][m][1]; } // M 方案枚举第二根木棒的长度 for (int m = 1; m <= k-1; m++){ dp[i][k][1] += dp[i-1][m][0]; } } } // 标记是否已经使用 bool visited[21] = {false}; // 保存结果的排列 int a[21]; // 逐一确定第 i 位 for(int i = 1; i <= n; i++) { int k = 0; // 假设第 i 放 j for(int j=1;j<=n;j++) { long long tmp = s; // 已经使用过的数不能再使用了 if(!visited[j]) { // j 是没有使用过的木棒中第 k 短的 k++; if(i == 1) { // 确定第一根木棒的长度 tmp -= dp[n][k][0] + dp[n][k][1]; } else if(j < a[i-1] && (i==2 || a[i-2]<a[i-1])) { // W 类型 tmp -= dp[n-i+1][k][0]; } else if(j > a[i-1] && (i==2 || a[i-2]>a[i-1])) { // M 类型 tmp -= dp[n-i+1][k][1]; } if(tmp <= 0) { visited[j]=true; a[i]=j; // 第 i 位为 j break; } } s = tmp; } } // 将结果转换为指定格式 vector<int> res; for(int i = 1; i <= n; i++) { res.push_back(a[i]); } return res; } }; 复杂度分析 最开始初始化dp数组时用了 O(2n2)O(2n^2)O(2n2) 的时间，随后填写dp数组花的时间为 O(n3)O(n^3)O(n3)，计算最终答案的时间为 O(n2)O(n^2)O(n2)，将结果转为指定格式的时间为 O(n)O(n)O(n)，所以该算法的时间复杂度为 O(n3)O(n^3)O(n3)。 dp数组占用了 O(2n2)O(2n^2)O(2n2) 的空间，标记数组visited、保存结果的数组a，以及最终转换为指定格式的path向量，各占用了 O(n)O(n)O(n) 的空间，取最大值即该算法的空间复杂度为 O(2n2)O(2n^2)O(2n2)，去掉系数得到最终空间复杂度 O(n2)O(n^2)O(n2)。

求几个整数的最大公约数大致有三种方法，求多个整数的最大公约数可以拆分为求两个整数的最大公约数，所以核心问题还是求两个整数的最大公约数。 穷举法 很直观就能想到穷举法，先找出两个数字中比较小的那一个min，然后逐个验证从2 ~ min的数字是否能被两个数整除，如果能同时被两个数字整除那就是公约数，找出其中最大的那个公约数就是所求的结果。 int gcd(int a, int b){ int min = a; if(b < a){ min = b; } for(int i = min; i > 2; i--){ if(a%i == 0 && b%i == 0){ return i; } } return 1; } 辗转相除法 辗转相除法是欧几里得想出来的，所以也叫做欧几里得算法。它的证明过程依赖于一个定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数，即gcd(a, b) = gcd(b, a mod b)，其中 gcd 表示最大公约数，此处假设 a > b。其证明过程如下所示： 设 c = gcd(a, b)； 则存在 m，n，使 a = mc，b = nc； 令 r = a mod b； 则存在 k，使 r = a - kb = mc - knc = (m - kn)c； 所以 gcd(b, a mod b) = gcd(b, r) = gcd(nc, (m-kn)c) = gcd(n, m-kn)c； 所以 c 为 b 与 a mod b 的公约数； 设 d = gcd(n, m-kn)； 则存在 x，y，使 n = xd，m-kn = yd； 所以 m = yd + kn = yd + kxd = (y + kx)d； 所以 a = mc = (y + kx)dc，b = nc = xdc； 所以 gcd(a, b) = gcd((y+kx)dc, xdc) = gcd(y+kx, x)dc = dc； 因为 gcd(a, b) = c，所以 d = 1； 即 gcd(n, m-kn) = 1，所以 gcd(b, a mod b) = c； 所以 gcd(a, b) = gcd(b, a mod b)； 证明 gcd(y+kx, x)dc = dc，即 gcd(y+kx, x) = 1： 前提条件：gcd(x, y) = 1； 假设 gcd(y+kx, x) != 1，则肯定 gcd(y+kx, x) > 1，设 gcd(y+kx, x) = i； 则 y+kx = ui，x = vi； 则 y = ui - kx = ui - kvi = (u-kv)i 则 gcd(x, y) = gcd(vi, (u-kv)i) = gcd(v, u-kv)i 因为 gcd(y+kx, x) = i > 1，gcd(v, u-kv) >= 1； 所以 gcd(x, y) > 1，与前提条件矛盾； 所以 gcd(y+kx, x) = 1 有了上面的基础之后，我们就可以总结出来一个算法实现的步骤了。设 r = a % b；如果 r 为 0 的话，那么 a 和 b 的最大公约数就是 b，否则就是求 b 和 a%b 的最大公约数。 // 递归写法 int gcd(int a, int b){ // 用 b 来存储 a%b 的值 if(b == 0){ return a; } return gcd(b, a%b); } // 迭代写法 int gcd(int a, int b){ while(b != 0){ int t = b; a = t; b = a % b; } return a; } 可以看到在算法实现过程中并没有先找出来最小的数字，这是因为程序会自动将最较大的那个数字放到 a 的位置，比如将gcd(75, 1000)带入我们的递归算法中则会变成gcd(1000, 75)。 辗转相减法 辗转相减法也叫更相减损术（尼考曼彻斯法），也是一种简便的求两个数的最大公约数的算法，它的特色是做一系列减法，从而求的最大公约数。比如两个自然数 36 和 27，用大数减去小数得 9 和 27，这时 9 小于 27，需要将两数交换即得 27 和 9，继续相减可得 18 和 9，然后 9 和 9，这时就可以得到两数的最大公约数为 9 了。其证明过程如下所示： 设 gcd(a, b) = x，a > b； 则有 a = mx，b = nx，m，n 均为正整数且 m > n； c = a - b = mx - nx = (m - n)x； 因为 a 和 b 均为正整数，所以 c 也能被 x 整除； 所以 gcd(a, b) = gcd(b, a-b) 具体的算法实现步骤在第一段已经有一个比较清晰的例子了，这里可以直接给出实现代码。 // 递归写法 int gcd(int a, int b){ if(a == b){ return a; } return a > b ? gcd(a-b, b) : gcd(a, b-a); } // 迭代写法 int gcd(int a, int b){ while(a != b){ a > b ? a = a - b : b = b - a; } return a; }

Bootstrap-table 官方提供了合并单元格方法 mergeCells，它根据四个参数可以合并任意个单元格，我们要做的只是告诉它怎么合并。 要合并同一列相同的单元格，无非两种办法，一种是一边遍历一边合并，遍历完了再合并。这里采用第二种办法，这里不需要遍历所有数据，因为用户只能看到当前页的数据，所以只遍历当前页的数据更省时间。 下面是我实现的获取合并信息算法，最终返回的是一个哈希表，比如下面的这个表格，如果要对「性别」这一列进行合并，很明显前面两个“男”需要合并成一个单元格，再去看下 Bootstrap-table 提供的 API，它需要的是从哪个单元格开始，合并多少个单元格，也就是它需要的是两个数值类型的参数。 姓名 性别 年龄 张三 男 23 李四 男 19 王二 女 20 麻子 男 21 所以我把哈希表设置为，键存的是索引，值存的是从这个索引开始后面连续有多少个和它一样的单元格，那么上述表格性别这一列所得到的合并信息哈希表就为： { 0: 2, 2: 1, 3: 1 } 下面算法很简单，使用两个指针遍历指定的列，如果两个指针所指向的数据相同，那么就将键所对应的值进行加一操作，整个方法只会对该列数据遍历一边，所以时间复杂度为 O(n)。 let getMergeMap = function (data, index: number) { let preMergeMap = {}; // 第 0 项为表头，索引从 2 开始为了防止数组越界 for (let i = 2; i < data.length; i++) { let preText = $(data[i-1]).find('td')[index].innerText; let curText = $(data[i]).find('td')[index].innerText; let key = i - 2; preMergeMap[key] = 1; while ((preText == curText) && (i < data.length-1)) { preMergeMap[key] = parseInt(preMergeMap[key]) + 1; i++; preText = $(data[i - 1]).find('td')[index].innerText; curText = $(data[i]).find('td')[index].innerText; } // while循环跳出后，数组最后一项没有判断 if (preText == curText) { preMergeMap[key] = parseInt(preMergeMap[key]) + 1; } } return preMergeMap; } 上述算法得到了单列数据的合并信息，下一步就是按照这个信息进行相同单元格的合并了，因此封装了下面的方法按照指定哈希表进行合并。 let mergeCells = function (preMergeMap: Object, target, fieldName: string) { for (let prop in preMergeMap) { let count = preMergeMap[prop]; target.bootstrapTable('mergeCells', { index: parseInt(prop), field: fieldName, rowspan: count }); } } 到目前为止，我们实现的都只是对单列数据进行合并，要实现对多列数据进行合并，那么只需要对所有列都进行相同的操作即可。 export let mergeCellsByFields = function (data: Object[], target, fields) { for (let i = 0; i < fields.length; i++) { let field = fields[i]; // 保证 field 与 i 是相对应的 let preMergeMap = getMergeMap(data, i); let table = target.bootstrapTable(); mergeCells(preMergeMap, table, field); } } 因为我在程序中做了一点处理，保证了fields中每个值得索引与对应表头的索引是一样的，因此不需要额外传入索引信息。简单来说就是我所实现的表格会根据fields的顺序，实现列之间的动态排序。你需要注意的是这一点很可能和你不一样。 到现在已经能够合并所有的列了，查看 Bootstrap-table 的配置信息发现，它有个属性是 onPostBody 它会在 table body 加载完成是触发，所以把这个属性配置成我们的合并单元格方法即可。 // groups 为要合并的哪些列 onPostBody: function () { mergeCellsByFields($('#table' + ' tr'), $('#table'), groups); } 再说一点不太相关的，我实现的是让用户可以自己选可以合并多少列，即用了一个可多选的下拉列表框供用户选择，根据用户选择的数量去合并，所以传入了一个groups参数。 最后推荐一个排序插件 thenBy，你可以用它进行多字段排序，比如用在合并相同单元格的场景，在绘制表格前先对数据进行排序，那么最后合并的结果就是把所有相同的数据聚合到一起了，并且还将它们合并到一起了，起到了一个隐形的过滤查询功能。

今天在群里看到一个有意思的问题——为什么处理排序数组比处理没有排序的数组要快，这个问题来源于 StackoverFlow，虽然我看到代码略微知道原因，但是模模糊糊不够清晰，搜了很多博客也讲的不够明白，所以就自己来总结了。 首先来看一下问题，下面是很简单的一段代码，随机生成一些数字，对其中大于 128 的元素求和，记录并打印求和所用时间。 import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } } 我的运行结果：分别在对数组排序和不排序的前提下测试，在不排序时所用的时间比先排好序所用时间平均要多 10 ms。这不是巧合，而是必然的结果。 问题就出在那个if判断上面，在旧文顺序、条件、循环语句的底层解释中其实已经提到了造成这种结果的原因，只是旧文中没有拿出具体的例子来说明。 为了把这个问题搞明白，需要先对流水线有一定的了解。计算机是指令流驱动的，执行的是一个一个的指令，而执行一条指令，又要经过取指、译码、执行、访存、写回、更新六个阶段（不同的划分方式所包含的阶段不一样）。 六个阶段使用的硬件基本是不一样的，如果一条指令执行完再去执行另一条指令，那么在这段时间里会有很多硬件处于空闲状态，要使计算机的速度变快，那么就不能让硬件停下来，所以有了流水线技术。 流水线技术通过将指令重叠来实现几条指令并行处理，下图表示的是三阶段指令时序，即把一个指令分为三个阶段。在第一条指令的 B 阶段，A 阶段相关的硬件是空闲的，于是可以将第二条指令的 A 阶段提前操作。 很明显，这种设计大幅提高了指令运行的效率，聪明的你可能发现问题了，要是不知道下一条指令是什么怎么办，那提前的阶段也就白干了，那样流水线不就失效了？没错，这就是导致开篇问题的原因。 让流水线出问题的情况有三种： 数据相关，后一条指令需要用到前一条指令的运算结果； 控制相关，比如无条件跳转，跳转的地址需要在译码阶段才能知道，所以跳转之后已经被取出的指令流水就需要清空； 结构相关，由于一些指令需要的时钟周期长（比如浮点运算等），长时间占用硬件，导致之后的指令无法进入译码等阶段，即它们在争用同一套硬件。 代码中的if (data[c] >= 128)翻译成机器语言就是跳转指令，处理器事先并不知道要跳转到哪个分支，那难道就等知道了才开始下一条指令的取指工作吗？处理器选择了假装知道会跳转到哪个分支（不是谦虚，是真的假装知道），如果猜中了是运气好，而没有猜中那就浪费一点时间重新来干。 没有排序的数组，元素是随机排列的，每次data[c] >= 128的结果也是随机的，前面的经验就不可参考，所以下一次执行到这里理论上还是会有 50% 的可能会猜错，猜错了肯定就需要花时间来修改犯下的错误，自然就会浪费更多的时间。 对于排好序的数组，开始几次也需要靠猜，但是猜着猜着发现有规律啊，每次都是往同一个分支跳转，所以以后基本上每次都能猜中，当遍历到与 128 分界的地方，才会出现猜不中的情况，但是猜几次之后，发现这又有规律啊，每次都是朝着另外一个相同分支走的。 虽然都会猜错，但是在排好序的情况下猜错的几率远远小于未排序时的几率，最终呈现的结果就是处理排序数组比未排序数组快，其原因就是流水线发生了大量的控制相关现象，下面通俗一点，加深一下理解。 远在他方心仪多年的姑娘突然告诉你，其实她也喜欢你，激动的你三天三夜睡不着觉，决定开车前往她的城市，要和她待在一起，但是要去的路上有很多很多岔路，你只能使用的某某地图导航，作为老司机并且怀着立马要见到爱人心情的你，开车超快，什么样罚单都不在乎了。 地图定位已经跟不上你的速度了，为了尽快到达，遇到岔路你都是随机选一条路前进，遗憾的是，自己的选择不一定对（我们假设高速可以回退），走错路了就要重新回到分岔点，这就对应着未排序的情况。 现在岔路是有规律的，告诉你开始一直朝着一边走，到某个地点后会一直朝着另一边走，你只需要花点时间去探索一下开始朝左边还是右边，到了中间哪个地点会改变方向就可以了，相比之下就能节省不少时间了，尽快见到自己的爱人，这对应着排好序的情况。 最后的故事改编自两个人的现实生活，一位是自己最好的朋友之一，谈恋爱开心的睡不着觉；另一位是微信上的一位好友，为了对方从北京裸辞飞到了深圳。

这是我的人生处女面遇到的一个面试题，是在去哪儿网二面遇到的，那时非常的紧张，还没有复习，所以第一次面试理所应当的挂了。文章对问题进行逐步的由简到难进行优化，基本上是代码，看懂代码才能理解，也为类似问题提供了基本的解决思路。 题目描述： 让你把一张整钱找零，即假设你拥有不同且不限量的小额钱币，你需要统计共有多少种方法可以用手中的小额钱币兑等额兑换一张大额钱币。 即：给定一个元素为正数的集合（元素不重复）代表不同面值的钱币，再给一个整数，代表要找零的钱数，求共有多少种换钱方法？ 递归求解 现在有1、5、10元三种面值的纸币，需要找零100元，那么可以做如下分析： 用 0 张 5 元换，剩下的用 1、10 元换，最终方法数为 count0； 用 1 张 5 元换，剩下的用 1、10 元换，最终方法数为 count1； ...... 用 100 张 5 元换，剩下的用 1、10 元换，最终方法数为 count100； 最终的换钱方法总数就为 count0 + count1 + ...... + count100。 根据上面的分析可以写出下面的递归解决方案： public static int coin(int money[], int target){ if (money == null || money.length == 0 || target < 0){ return 0; }else { return slove(money, 0, target); } } // 用money[index, length-1]换钱，返回总的方法数 private static int slove(int money[], int index, int target){ int res = 0; if(index == money.length){ if (target == 0){ res = 1; }else { res = 0; } }else { for (int i = 0; money[index] * i <= target; i++) { res += slove(money, index+1, target-money[index]*i); } } return res; } 优化递归 可以看到，上面的程序在运行时存在大量的重复过程，比如下面两种情况，其后所求结果是一样的。 兑换 100 元，已经使用了 0 张 1 元、1 张 2 元，剩下的用 5 元和 10 元兑换； 兑换 100 元，已经使用了 2 张 1 元、0 张 2 元，剩下的用 5 元和 10 元兑换； 可以发现，这两种情况后面都是求解同一问题，重复的对同一个问题求解，就造成了时间的浪费，因此我们可以考虑将已经计算过的结果存下来，避免重复的计算，所以有下面的优化方案。 public static int coin(int money[], int target){ if (money == null || money.length == 0 || target < 0){ return 0; }else { /** * map[i][j]表示p(i,j)递归回的值 * 其中-1表示该递归过程计算过，但是返回值为0 * 0表示该递归过程还为计算过 */ int map[][] = new int[money.length+1][target+1]; return slove(money, 0, target, map); } } private static int slove(int money[], int index, int target, int map[][]){ int res = 0; if(index == money.length){ if (target == 0){ res = 1; }else { res = 0; } }else { int val = 0; for (int i = 0; money[index] * i <= target; i++) { val = map[index + 1][target - money[index]*i]; if (val != 0){ if (val == -1){ res += 0; }else { res += val; } }else { res += slove(money, index+1, target-money[index]*i, map); } } } if (res == 0){ map[index][target] = -1; }else { map[index][target] = res; } return res; } 动态规划 上面对递归方法的优化已经能看到动态规划的影子了，这是一个二维的动态规划问题，我们定义dp[i][j]的含义为：使用money[0...i]的钱币组成钱数j的方法数。所以可以得出以下面的动态规划解法： public static int coin(int money[], int target){ if (money == null || money.length == 0 || target < 0){ return 0; } int dp[][] = new int[money.length][target+1]; // 第一列表示组成钱数为0的方法数，所以为1 for (int i = 0; i < money.length; i++) { dp[i][0] = 1; } // 第一行表示只使用money[0]一种钱币兑换钱数为i的方法数 // 所以是money[0]的倍数的位置为1，否则为0 for (int i = 1; money[0] * i <= target; i++) { dp[0][money[0] * i] = 1; } for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[0].length; j++) { for (int k = 0; j >= money[i] * k; k++) { // dp[i][j]的值即为，用money[0...i-1]的钱 // 组成j减去money[i]的倍数的方法数 dp[i][j] += dp[i-1][j-money[i]*k]; } } } return dp[money.length-1][target]; } 继续优化 可以发现上面的动态规划解法有三层循环，因为是二维的动态规划问题，前两层没办法去掉，但是第三层依旧很耗时间，继续优化可以得到下面的结果。 public static int coin(int money[], int target){ if (money == null || money.length == 0 || target < 0){ return 0; } int dp[][] = new int[money.length][target+1]; for (int i = 0; i < money.length; i++) { dp[i][0] = 1; } for (int i = 1; money[0] * i <= target; i++) { dp[0][money[0] * i] = 1; } for (int i = 1; i < money.length; i++) { for (int j = 1; j <= target; j++) { /** * 通过分析可以发现，dp[i][j]的值由两部分组成 * 1：用money[0...i-1]的钱组成钱数为j的方法数 * 2：用money[0...i]的钱组成钱数为j-money[i]*k（k=1,2,3....）的方法数 * 对于第2种情况，实际上累加的值就是dp[i][j-money[i]] * 所以直接使用dp[i][j-money[i]]即可 */ dp[i][j] = dp[i-1][j]; if (j >= money[i]){ dp[i][j] += dp[i][j-money[i]]; } } } return dp[money.length-1][target]; } 空间压缩 可以看到每次更新dp[i][j]，dp[i][j]的值只与前一行和当前行前面的元素有关系，而我们只需要最后的一个结果就行了，那么前面存的元素实际上会造成空间的浪费，进一步可以在空间上进行优化。 我们只需要定义一个一位数组，然后对该数组进行滚动更新就可以了，只要按照合适方向去更新数组，同样能达到上面的效果。 public static int coin(int money[], int target){ if (money == null || money.length == 0 || target < 0){ return 0; } int dp[] = new int[target+1]; // 第一行，只用money[0]兑换钱 // 所以只能兑换为money[0]的倍数，将这些位置置为1 for (int i = 0; money[0]*i <= target; i++) { dp[i] = 1; } for (int i = 1; i < money.length; i++) { for (int j = 1; j <= target; j++) { // 与前一步相比，少了dp[i][j] = dp[i-1][j]; // 因为这里在进行dp[j] += dp[j-money[i]];之前 // dp[j]的值就已经是dp[i-1][j]了 if (j >= money[i]){ dp[j] += dp[j-money[i]]; } } } return dp[target]; } 到这一步就不再有优化空间了，这个问题很值得记录下来，很多笔试、面试题都可以按这个模子进行套，对于只需要最优解的动态规划问题也可以套用上面的空间压缩思路，多总结、多练习总是没有问题的！这个解题思路第一次看到是左程云在牛客网上讲解的，他也写了一本算法相关的书比较不错，叫做程序员代码面试指南，大四、研三、刚入职的新人建议可以买一本读读，对自己编码技能的提升绝对又很大的帮助。