动态规划实现相邻生物融合最大可爱值求解求助

问题分析 #

贪心算法无法得到最优解，因为局部最优的合并选择不一定能带来全局最优的最终结果。这个问题适合用动态规划解决，核心是记录每个区间合并后的最大可爱值以及对应的左/右亲和度——因为合并两个子区间时，得分计算依赖于子区间的这三个属性。

动态规划思路 #

定义三个二维数组：

• dp[i][j]：合并第i到第j个生物后得到的最大可爱值
• left[i][j]：合并i到j后生物的左亲和度
• right[i][j]：合并i到j后生物的右亲和度

状态转移 #

1. 基础情况：当i == j（单个生物），直接取自身属性：

   dp[i][j] = fitmons[i][1]
   left[i][j] = fitmons[i][0]
   right[i][j] = fitmons[i][2]
   

2. 区间合并：对于长度大于1的区间[i,j]，遍历所有分割点k（i ≤ k < j），计算合并[i,k]和[k+1,j]的得分，选择能得到最大可爱值的分割方式：

   current_score = dp[i][k] * right[i][k] + dp[k+1][j] * left[k+1][j]
   

   取所有k对应的current_score的最大值作为dp[i][j]，同时记录对应的left[i][j] = left[i][k]，right[i][j] = right[k+1][j]。

完整实现代码 #

def fuse(fitmons: list[list]) -> float:
    n = len(fitmons)
    if n == 0:
        return 0.0
    if n == 1:
        return fitmons[0][1]
    
    # 初始化DP数组和亲和度记录数组
    dp = [[0.0 for _ in range(n)] for _ in range(n)]
    left = [[0.0 for _ in range(n)] for _ in range(n)]
    right = [[0.0 for _ in range(n)] for _ in range(n)]
    
    # 单个生物的情况
    for i in range(n):
        dp[i][i] = fitmons[i][1]
        left[i][i] = fitmons[i][0]
        right[i][i] = fitmons[i][2]
    
    # 按区间长度从小到大计算
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            max_cute = 0.0
            # 遍历所有可能的分割点
            for k in range(i, j):
                # 计算合并两个子区间的得分
                current = dp[i][k] * right[i][k] + dp[k+1][j] * left[k+1][j]
                if current > max_cute:
                    max_cute = current
                    # 更新当前区间的亲和度
                    left[i][j] = left[i][k]
                    right[i][j] = right[k+1][j]
            dp[i][j] = max_cute
    
    return dp[0][n-1]

# 测试示例
fitmons = [[0, 255, 0.38], [0.38, 836, 0.36], [0.36, 152, 0.79], [0.79, 38, 0.82], [0.82, 303, 0]] 
print(fuse(fitmons))

代码说明 #

1. 先处理边界情况：空数组返回0，单个生物直接返回其可爱值。
2. 初始化三个二维数组，分别存储每个区间的最大可爱值、左亲和度、右亲和度。
3. 先填充单个生物的基础状态。
4. 按区间长度从2到n依次计算，确保计算长区间时，所有子区间的结果已经得出。
5. 对每个区间，遍历所有可能的分割点，计算合并得分，保留最大值并更新对应的亲和度。
6. 最终dp[0][n-1]就是合并所有生物后的最大可爱值。

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