九章算法 | 微软面试题：石子归并
最新回答
路人
2024-11-23 10:33:16
实例1展示如何应用策略。
实例2进一步说明问题。
采用区间动态规划（DP）解决此问题。状态表示为s，表示石头重量数组，f[i][j]表示合并s[i,...,j]石子所需的最少能量。
根据最后一步合并操作，f[i][j]的计算有以下两种情况：
1. 最后一步合并s[i]和s[i+1,...,j]。总能量为f[i+1][j]+sum(s[i]...s[j])。s[i]自身无需合并。
2. 最后一步合并s[i,i+1]和s[i+2,...,j]。总能量为f[i][i+1]+f[i+2][j]+sum(s[i]...s[j])。合并前两堆后，再合并剩余石子。
规律显示，f[i][j]为所有可能区间分法中，前半区间合并能量加上后半区间合并能量，再加最后一次合并所需能量。
复杂度分析及更多题解参考九章算法。
热门标签
