摘要: 參考了下別人的代碼，dp真是千變萬化?。?
這與搬寢室還是有很大不同的，要倒過來做；
dp[物品組數][物品個數](I為I副筷子，J為總共筷子)
現在轉入正題,這個題目要求每一組有3個筷子,前2個的差的平方最小,
首先和前面題目一樣先排序對把,顯然從大到小排(因為這樣完全可以轉化成搬寢室 那個一樣的思想)
比如取第2隊物品,那么第一對已經取完保存在數組里面了,
那么從s[2][3*2+1]計算到s[2][n],
為什么這樣就可以呢?
仔細想下,第2組,前面只要有2個可以作為最大的筷子了,一定滿足題目意思的了,所以一直計算下去,
狀態轉移方程和前面一樣~
dp[i][j]=min(dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]),dp[i][j-1]);
ps:排序從大到小很精妙~
閱讀全文