求索引和为k的n个元素最小和：高效解法及DP实现咨询

问题描述 #

给定n个非负整数组成的升序数组，需找到n个索引（每个数组对应一个），满足：

1. 所有索引的和等于给定的k
2. 这些索引对应的元素之和最小

示例 #

示例1 #

a = [0, 3, 5, 7, 10]
b = [0, 5]
c = [0, 10, 11, 12, 13, 18]
k = 7 

ans = [3, 0, 4] # a[3] + b[0] + c[4] = 7+0+13=20，为最小可能值
# 索引和：3+0+4=7=k

示例2 #

a = [0, 3, 6, 7, 9, 10]
b = [0, 1, 4, 7, 9, 10]
c = [0, 2, 3, 6, 7, 9 ]
k = 10

ans = [5, 1, 4] # 最小元素和=10+1+7=18
# 索引和：5+1+4=10=k

常见误区：贪心策略不可行 #

尝试过每步选择当前最小元素的贪心思路，但无法得到正确结果——局部最优无法保证全局最优，比如为了后续能将更多索引分配到元素增长更慢的数组，可能需要当前选择稍大的元素。

高效解法：动态规划 #

你猜测的动态规划思路完全可行，以下是具体实现方案：

状态定义 #

定义dp[j][s]表示：考虑前j个数组时，选取的索引之和为s的最小元素和。

转移方程 #

对于第j个数组（从1开始计数），遍历所有可能的索引t（满足t <= len(arr[j-1])-1且t <= s），则：
dp[j][s] = min(dp[j][s], dp[j-1][s - t] + arr[j-1][t])

初始状态：

• dp[0][0] = 0：前0个数组，索引和为0时元素和为0
• 其余dp[0][s>0]设为无穷大（表示不可能的状态）

空间优化 #

因为计算dp[j][*]只需要dp[j-1][*]的数据，所以可以用一维数组滚动更新：

• 初始化dp[s]为无穷大，dp[0] = 0
• 对于每个数组，从s = k倒序遍历到0（避免覆盖上一轮未使用的数据）：
  • 遍历当前数组的索引t（t <= s且t < len(arr)）：
    • dp[s] = min(dp[s], dp[s - t] + arr[t])

带路径还原的代码实现（Python） #

def find_min_sum_indices(arrays, k):
    n = len(arrays)
    # dp[s]：当前考虑过的数组中，索引和为s的最小元素和
    dp = [float('inf')] * (k + 1)
    dp[0] = 0
    # path[j][s]：前j个数组索引和为s时，第j个数组选择的索引
    path = [[-1]*(k+1) for _ in range(n)]
    
    for j in range(n):
        arr = arrays[j]
        new_dp = dp.copy()
        # 倒序遍历s，防止重复利用当前数组的元素
        for s in range(k, -1, -1):
            if dp[s] == float('inf'):
                continue
            # 当前数组能选的最大索引：不超过数组长度-1，且加上s不超过k
            max_t = min(len(arr)-1, k - s)
            for t in range(1, max_t + 1):
                if new_dp[s + t] > dp[s] + arr[t]:
                    new_dp[s + t] = dp[s] + arr[t]
                    path[j][s + t] = t
        dp = new_dp
    
    # 回溯推导具体索引
    indices = []
    current_s = k
    for j in range(n-1, -1, -1):
        t = path[j][current_s]
        if t == -1:
            indices.append(0)
        else:
            indices.append(t)
            current_s -= t
    indices.reverse()
    return indices

# 测试示例1
arrays1 = [[0,3,5,7,10], [0,5], [0,10,11,12,13,18]]
k1 =7
print(find_min_sum_indices(arrays1, k1)) # 输出[3,0,4]

# 测试示例2
arrays2 = [[0,3,6,7,9,10], [0,1,4,7,9,10], [0,2,3,6,7,9]]
k2=10
print(find_min_sum_indices(arrays2, k2)) # 输出[5,1,4]

复杂度分析 #

• 时间复杂度：O(n * k * m)，其中n是数组个数，k是目标索引和，m是单个数组的平均长度。若数组长度远大于k，m可近似为k，此时复杂度为O(n*k²)。
• 空间复杂度：O(n*k)（带路径记录）；若无需路径，用滚动数组可将空间压缩至O(k)。

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