本文主要是介绍问题 C: 搬寝室（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法分析：
题目意思为求n个物品，拿k对使得消耗的体力最少，
或者说是这k对物品，每一对中两件物品的质量差平方最小，
所以要使得质量差的平方小，只能排序后取质量相邻两个物品作为一对；
现在设f[i][j]为前i件物品组成k对所消耗的体力最小；
这时分两种情况含有第i件物品和不含有第i件物品（即第i件物品是不是含在第j对里）
1.含有i件物品 则有 f[i][j]=f[i-1][j-2]+(val[i]-val[i-1])*(val[i]-val[i-1]);
2.不含第i件物品则有 f[i][j]=;
所以动态转移方程为:
f[i][j]=
minn( f[i-1][j-2]+(val[i]-val[i-1])*(val[i]-val[i-1]) , f[i][j-1];
状态转移方程实现：
（但有个漏洞，每对第一个元素计算所用的 f[i-1][j-2]，未赋值）
f[i-1][j-2]+(val[i]-val[i-1])*(val[i]-val[i-1]) 中的 f[i-1][j-2]默认为0
存在0+(val[i]-val[i-1])*(val[i]-val[i-1]) < f[i][j-1] 的情况
（取前一两对不会出错，多对就会出错）
这篇关于问题 C: 搬寝室（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
