美团后端开发进度

第四题是dp题：例如 6 4 1 4 3 7 6 2 题解如下： 1.首先删除4个数等价于留下2个数。 2.跟数组顺序无关，因此先将数组排序成：1 2 3 4 6 7 3.枚举每个元素a比其大的且成倍数关系的元素，例如： 1有｛2,3,4,6,7｝ 2有{2,4,6} 3有{6} 4有｛｝ 6有｛｝ 7有｛｝ 4.推导状态转移方程，先思考留下1个数，当留下1个数的时候，dp[i][1]的方案数都等于1。留下2个数，对于每一个元素，只要累加比其大且成倍数关系的元素j的dp[j][2-1]即可。此时dp[1][2]等于5、dp[2][2]等于3、dp[3][2]等于1，其余元素都是0，将其加起来就是8，就等于方案数。依次类推到n，时间复杂度O（n^2）。

第五题直接输出n/2就过了

第四题二维dp

第四题dp就行，因为要删k个就是留n-k个，循环n-k次，可以理解成每次循环找到保留i个数时以当前数为结尾的序列个数。 每次用一个一维数组tmp记录能除尽当前数的所有数的dp和，记录完后用tmp覆盖dp数组进入下一轮。不过直接这么写会超时，我是把每个数对应的能除尽他的数的下标额外存进了一个二维数组，这样每次tmp数组只要遍历那个数对应的下标数组就行。就100%了