这个问题本质上是动态规划的典型应用，我们需要找到一条通过指定步长移动的路径，使得收集到的楼梯价值总和最大。下面我会一步步拆解思路，结合示例给出解法和可运行的代码。

核心思路 #

我们可以用动态规划数组dp来记录到达每一级楼梯时能获得的最大价值：

• 定义dp[i]为到达第i级楼梯（数组索引从0开始）时的最大累计价值。
• 对于每一级楼梯i，能到达它的方式是从i-s的位置跳s步过来（s属于可行步长集合）。如果i-s是-1，说明是从起始位置（未踩任何楼梯）直接跳s步到达i。
• 状态转移方程：dp[i] = staircase[i] + max( dp[i-s] if i-s >=0 else 0 for s in possible_steps if i-s >= -1 )

同时，为了还原最优步长序列，我们需要额外记录每个位置的前驱节点（即从哪个位置跳过来的），最后通过回溯得到完整的步长路径。

示例计算过程 #

拿题目中的例子来说：

• staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64]
• possible_steps = {3,4,5}

我们逐个计算dp数组的值：

• dp[0]：没有步长能从起始位置跳到这里（需要步长1），所以值为0
• dp[1]：同理，需要步长2，不在集合中，值为0
• dp[2]：可以通过步长3从起始位置跳到这里，值为44 + 0 = 44
• dp[3]：可以通过步长4从起始位置跳到这里，值为5 + 0 =5
• dp[4]：可以通过步长5从起始位置跳到这里，值为12 +0=12
• dp[5]：最优路径是从dp[2]跳3步过来，值为34 +44=78
• dp[6]：最优路径是从dp[2]跳4步过来，值为55+44=99（对应示例中的[3,4]序列）
• dp[7]：最优路径是从dp[2]跳5步过来，值为45+44=89
• dp[8]：最优路径是从dp[5]跳3步过来，值为23+78=101
• dp[9]：最优路径是从dp[6]跳3步过来，值为64+99=163

这里的最大价值是163，对应的步长序列是[3,4,3]（先跳3步到索引2，再跳4步到索引6，最后跳3步到索引9）。

代码实现 #

下面是Python的完整实现，包含最大价值计算和最优步长序列的还原：

def max_staircase_value(staircase, possible_steps):
    n = len(staircase)
    if n == 0:
        return 0, []
    
    dp = [0] * n
    prev = [-1] * n  # 记录每个位置的前驱索引
    
    for i in range(n):
        for s in possible_steps:
            prev_idx = i - s
            # 计算当前路径的价值
            if prev_idx == -1:
                current_total = staircase[i]
            elif prev_idx >= 0:
                current_total = staircase[i] + dp[prev_idx]
            else:
                continue  # 步长过大，无法到达当前位置
            
            # 更新dp和前驱记录
            if current_total > dp[i]:
                dp[i] = current_total
                prev[i] = prev_idx
    
    # 找到最大价值对应的位置
    max_val = max(dp)
    max_idx = dp.index(max_val)
    
    # 回溯生成步长序列
    steps = []
    current = max_idx
    while current != -1:
        # 计算当前步长：当前索引 - 前驱索引
        step = current - prev[current] if prev[current] != -1 else current + 1
        steps.append(step)
        current = prev[current]
    
    # 反转得到顺序的步长序列
    steps.reverse()
    
    # 如果所有dp值都是0，说明无法到达任何楼梯，返回空序列
    if max_val == 0:
        return 0, []
    
    return max_val, steps

# 测试示例
staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64]
possible_steps = {3,4,5}
max_val, optimal_steps = max_staircase_value(staircase, possible_steps)
print(f"最大收集价值: {max_val}")
print(f"最优步长序列: {optimal_steps}")

运行这段代码会输出：

最大收集价值: 163
最优步长序列: [3, 4, 3]

复杂度分析 #

• 时间复杂度：O(n*k)，其中n是楼梯的级数，k是可行步长的数量。每个楼梯都需要遍历所有步长计算可能的路径价值。
• 空间复杂度：O(n)，用于存储dp数组和prev数组。

边界情况处理 #

• 当楼梯数组为空时，返回0和空序列。
• 当没有任何步长能到达任何楼梯时，最大价值为0，步长序列为空。
• 当步长包含1时，最优路径就是踩遍所有楼梯，总和为数组所有元素之和。

内容的提问来源于stack exchange，提问作者ljystack