拼多多学霸批后台第二批笔试

麻烦参加了拼多多这批笔试的大佬帮我分析一下下面的代码问题呀

第一次笔试紧张，第2，3题都没做出来，第4题都没时间看。

大家讨论一下呗。

"""
第2题
给定和S，要求得到一个长度为n的正整数递增序列 要求这个序列的和为S
输出满足以上要求的序列数目
eg. 输入 n, s = 2, 5 输出 2 因为满足条件的只有(1, 4), (2, 3)
算法：递推公式 dp[i][j][k] = sum(dp[i-1][1...j-1][x]) i表示序列长度 j表示给定和 k表示以k结尾的数 
解释: 因为要得到dp[i][j] 它是从长度为i-1的长度加上一个数k来的, 其中x<k
"""
def get_pre_sum(dp_i, j, k):
    res = 0
    for tmp_k in range(1, k):
        if j - k in dp_i.keys() and tmp_k in dp_i[j-k].keys():
            res += dp_i[j-k][tmp_k]
            res %= 1000000007
    return res
def suitable_sequence_count():
    """
    主程序
    """
    n, s = list(map(int, sys.stdin.readline().strip().split(' ')))
    dp = dict()   # 用字典hash存感觉比较方便
    tmp = dict()
    for i in range(s//n):
        tmp[i+1] = dict()
        tmp[i+1][i+1] = 1
    dp[1] = tmp   # 初始化 所有长度为1的和为s的都只有1个满足要求的序列
    # 按递推公式动态规划实现
    for i in range(1, n-1):
        for j in range(s):
            tmp = dict()
            k = 1
            while j - k + 1 > 0:
                tmp[j+1] = dict()
                tmp[j+1][k] = get_pre_sum(dp[i], j+1, k)
                k += 1
            if tmp:
                if i + 1 in dp:
                    dp[i+1][j+1] = tmp[j+1]
                else:
                    dp[i+1] = tmp
    res = 0
    if n <= 0 or s <= 0:  # 不合法输入
        res = 0
    elif n == 1:
        res = 1
    else:
        for k in range(1, s+1):
            res += get_pre_sum(dp[n-1], s, k)
    print(res)
"""  假设一个n长的项链，从0开始标记位置 该项链上共有p个珍珠(p<=n) 这些珍珠随机散落在项链上
求：把这个散落的珍珠汇聚在一起 即让他们连续摆放需要最少移动多少步
其中 0 和 n-1 位置视作相连续
eg. 输入 n=1000 p = 1, 4, 998, 995  输出 8  因为 1->0；4->1; 998->999;995->998共八步
算法: 要珍珠连续可以假设珍珠从i位置开始连续(i=[0, n))，要注意的情况是i <= n - p 这时候要从1开始循环 
    设置一个数组存放连续的位置[i...end]， 始终把i看作是中间的位置n//2 因为是环所以相对位置不变的 这样也方便计算
    所以从i开始连续的最小移动步数 = min(i位置之前的第一颗珠子移到i, i位置之后的第一颗珠子移动到i(包括i)）
"""
def pre_to_i_move(pre_i_purples, rear_i_purples, i, n):
    """
    用于计算i位置之前的第一颗珠子移到i所需步数
    :return:
    """
    move_times = 0
    for pos in pre_i_purples:
        move_times += (i - pos)
        i += 1  # 下一个位置需要移动 这里不取余是因为不可能pre_i_purles的数目超过一半
    for pos in rear_i_purples:
        move_times += abs(pos - i % n)  # 让i位置循环
        i += 1
    return move_times
def rear_to_i_move(pre_i_purples, rear_i_purples, i, n):
    """
    用于计算i位置之后的第一颗珠子移动到i(包括i)
    :return:
    """
    move_times = 0
    for pos in rear_i_purples:
        move_times += (pos - i)
        i += 1
    for pos in pre_i_purples[::-1]:
        move_times += (pos - i % n + n) % n
        i += 1
    return move_times
def purple_to_continue():
    """
    主程序
    """
    n = int(sys.stdin.readline().strip())
    purple_positions = list(map(int, sys.stdin.readline().strip().split(' ')))  # 初始输入的珍珠位置信息
    purple_positions.sort()   # 方便后面计算移动
    move_times = None
    pre_pos = None
    flag = True
    for pos in purple_positions:
        if pre_pos is not None and pos - pre_pos != 1:
            flag = False
            break
        pre_pos = pos
    if flag:  # 不用移动已经连续
        move_times = 0
    else:
        mid_pos = n // 2
        for i in range(n):
            redundance = mid_pos - i if i <= mid_pos else n - i + mid_pos  # 为了把i位置看作是中间的位置方便计算
            pre_i_purples = []
            rear_i_purples = []
            for pos in purple_positions:  # 因为purple_positions是有序的遍历到某个位置的相对位置是不变的
                tmp_pos = (pos + redundance) % n
                if tmp_pos < mid_pos:
                    if pre_i_purples and pre_i_purples[0] > tmp_pos:
                        pre_i_purples.insert(0, tmp_pos)
                    else:
                        pre_i_purples.append(tmp_pos)
                else:
                    if rear_i_purples and rear_i_purples[0] > tmp_pos:
                        rear_i_purples.insert(0, tmp_pos)
                    else:
                        rear_i_purples.append(tmp_pos)
            tmp = min(pre_to_i_move(pre_i_purples, rear_i_purples, mid_pos, n),
                      rear_to_i_move(pre_i_purples, rear_i_purples, mid_pos, n))
            if move_times is None or move_times > tmp:
                move_times = tmp
    print(move_times)