第二题： 小明在学旋律，每段旋律都可以用字符串来表示，并且旋律的每个 字符的ASCALL码递增的 比如以下4段旋律 : aaa bcd bcdef zzz 现在就是要求，小明能够吧这些旋律拼接起来组成最长的旋律。 比如上述例子输出 11 最长的旋律为 aaabcdefzzz 这题看似简单，不就排个序，然后把第一个字符串的末尾字符小于第二个字符串首字符的两个字符串拼接起来就好了嘛，但是字符串之间可能出现交叉，比如 aaa bcd cdef 肯定是拼接cdef好而不是bcd。那么如何解决呢，这种最优解或最大路径问题，一般就要用到回溯法或者动态规划了。 回溯法就是走迷宫，遍历完所有路径，找出最优的那个路径就行 void nextMelody(vector<string> melodies, int n, int curLength) { if (n == melodies.size()) { return; } string curMelody = melodies[n]; curLength += curMelody.length(); maxLength = max(maxLength, curLength); char curMelodyLastChar = curMelody[curMelody.length() - 1]; for (int i = n + 1; i < melodies.size(); i++) { char nextMelodyFirstChar = melodies[i][0]; int cmp = curMelodyLastChar - nextMelodyFirstChar; if (cmp <= 0 && curLength + lengthLeft[i] > maxLength) { nextMelody(melodies, i, curLength); } } } 这是一个递归的回溯剪枝,lengthLeft[]和maxLength 是全局变量，分别用于纪录原数组中还剩的字符串总长度和目前以查找的最优路径，剪枝的条件前str[末]<str[头]且当前最优路径+还剩路径>maxLength （否则就不考虑了，肯定最优已经出来了） 动态规划和回溯差不多 不过可以从后往前，这样可以节省很多重复的开销，不过要开辟N的额外空间。时间效率上都差不多 int dynamicSolver(vector<string>& str) { //从后往前 int len = str.size(); //用于纪录路径最大和 int *dp=new int[len]; memset(dp, 0, sizeof(dp[0])); int maxlength=0; for (int i = len - 1; i >= 0; i--) { for (int j = i; j < len ; j++) { if (i == len - 1) { dp[i] = str[i].size(); if (dp[i] > maxlength) maxlength = dp[i]; } else if (str[i][str[i].size() - 1] <= str[j][0]) { dp[i] = max(dp[i], (int)(dp[j] + str[i].size())); if (dp[i] > maxlength) maxlength = dp[i]; } } } return maxlength; }

对了 因为我不是面试者，我只是刷一刷题 ，我只是重视思路，有些细节没注意到，比如说第一题要mod 10^9 第二题是求路径 我求的总和，思路应该是没问题的

第一题我也是这个思路，但是我通过率0。。

听说第一题可以推公式，n*2^(n-1)