核心思想
这是一道最长公共子序列(LCS)的变形题,不是求长度,而是求对应位置乘积和的最大值。
状态定义
* i 遍历序列A(0到N)
* j 遍历序列B(0到M)
* 初始值:全部设为 -INF(表示还没有合法方案)
状态转移(核心)
对于每个位置 (i, j),有三种决策:
1️⃣ 不选A[I](跳过A的当前数)
从 (i-1, j) 转移过来,相当于A往前退一步
2️⃣ 不选B[J](跳过B的当前数)
从 (i, j-1) 转移过来,相当于B往前退一步
3️⃣ 选择A[I]和B[J]配对(关键)
这一步有两种可能:
a) 这是第一对数
直接用这一对的乘积作为结果(满足"至少选1对")
b) 累加到之前的结果
如果 (i-1, j-1) 已经有合法方案,就累加当前这对的乘积
为什么这样写?
关键点1:自动处理"至少1对"
* 不用单独记录选了几对(省去第三维)
* 初始化为 -INF,只有真正配对后才有有效值
* 每次配对都考虑"作为第一对"或"累加到已有结果"
关键点2:保持子序列顺序
* dp[i-1][j-1] 确保了配对的两个数都是按原序列顺序选的
* 类似LCS,对角线转移保证顺序性
图解样例1
DP表推导(部分关键值):
代码