摘要: 題目大意：從n根筷子當(dāng)中選取j對(duì)，其中一對(duì)筷子包含三根，并且要求第三跟不短語(yǔ)前兩根。要求取出的筷子長(zhǎng)度差（前兩根的長(zhǎng)度差）的平方的和最小。
num[i] 表示第i+1個(gè)筷子與第i個(gè)筷子長(zhǎng)度差的平方~
開(kāi)始從前面往后推，漏洞百出:dp[i][j]表示從1……i個(gè)筷子中選取j對(duì)，
dp[i][j] = MIN(dp[i-1][j],dp[i-3][j-1] + num[i-2]);
問(wèn)題在哪？ 第i個(gè)筷子能用，
一種情況：第i-1個(gè)筷子能與第i-2個(gè)筷子配對(duì)了（來(lái)了第三根筷子i）；
二種情況：影響1……i-1個(gè)筷子中取j對(duì)筷子的配對(duì)情況。WHY？think about~
最后從后往前推:dp[i][j]表示從i……n個(gè)筷子中選取j對(duì)，
dp[i][j] = MIN(dp[i+1][j],dp[i+2][j-1] + num[i]);
沒(méi)問(wèn)題了吧~ 第i個(gè)筷子取，則必與第i+1個(gè)筷子配對(duì)，不取則可以忽略它（就因?yàn)樗钱?dāng)前最短的）
閱讀全文