4月12日 小红书后端笔试编程题解

选择题跳过。
编程题三题
T1 签到，排序去重即可。

T2 问刚好等于x。考虑01背包（下标从1开始）。
dp[i][j][k]表示到第i个数，总共选取了j个，k=0表示[1~i]都没多次操作（都没加倍）。k=1表示[1~i]存在加倍的情况，可能是i，也可能是之前的某次。
列出状态转移方程：
dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j-a[i]/2][0]+1) 表示不选和选的情况。
dp[i][j][1] = min(dp[i-1][j][1], dp[i-1][j-a[i]/2][1]+1, dp[i-1][j-a[i]][0]+1) 表示不选、选择但是不多次操作、选择并多次操作的情况。
最后输出min(dp[n][x][0],dp[n][x][1])即可，若为inf则输出-1.
第一维可以优化掉，空间O(x)，时间O(nx)。

T3 样例给的比较号是&lt;和&gt;这种，很神秘，最后发现直接改成<和>都行。
也考虑dp。
先把等号去掉，那个不影响答案。
假设有len个运算符
dp[i][j]表示到第i个运算符右侧的数，选择j，所得到的方案数。
如果第i个运算符是 > ，说明右侧的数更小，则 dp[i][j] = dp[i-1][j+1] + dp[i-1][j+2] + ... + dp[i-1][m]
如果第i个运算符是 < ，说明右侧的数更大，则 dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][1]
初始化dp[0][1~m] = 1，表示最左侧的数取任何数的方案数都是1
最后对dp[len][1~m]求和即可。

当然直接算会超时，毕竟要求和。
实际上如果第i个运算符是 >，那么由于dp[i][j+1] = dp[i-1][j+2] + ... + dp[i-1][m]，因此dp[i][j] = dp[i][j+1] + dp[i-1][j+1]。
同理如果第i个运算符是 < ，那么dp[i][j] = dp[i][j-1] + dp[i-1][j-1]。
由于i只用到2个，因此可以压缩一维到大小为2.
最后空间复杂度O(2*m) = O(m)，时间复杂度O(n*m)

#笔试##小红书#