動態(tài)規(guī)劃能量項鏈的 標程的循環(huán)不是很懂，求解釋~

【專家解說】：題意背景故事略蛋疼啊...其實這個事情的模型就是矩陣相乘吧，只不過對于矩陣來說，一般都是找乘法次數(shù)最少的組合，這里是找最多的 首先，你要了解動態(tài)規(guī)劃在這里的思路。先不考慮珠子可以循環(huán)這個性質(zhì)，假設珠子就是1,2,...,N這樣，那么我們就是要找(1,2,..,N)之中兩兩聚合的最大值，這個最大值應該在以下值當中產(chǎn)生: (1) 和 (2,3,...,N)聚合 (1,2)和(3,4,...N)聚合 .... (1,2,...N-1)和(n)聚合 也就是把1到N一切為二，前半段聚合成一個珠子，后半段聚合成一個珠子，再把聚合后的珠子做一次聚合。至于在哪里一分為二，就是最里面的for循環(huán)做的事情。它在i到j之中尋找一個k，使得i到k聚合的能量+(k+1)到j聚合的能量+前面兩個聚合出來的珠子聚合的能量 為最大值。而外面的兩個for循環(huán)，就是在做遍歷(i,j)這樣的二維組合，先算f(1,2)，在算f(2,3)這樣只相差1的，然后就可以算f(1,3)這樣i,j相差更大的f值了。我們的最終目標是算出f(1,N)的值，也即題目的答案 但是題目還有個條件，就是珠子可以循環(huán)，所以我們要在f(1,N),f(2,N+1),f(3,N+2),...,f(N,2N-1)這之間找一個最大值。這也就是為什么一開始 e[N+i]=e[i]; 以及第一個for循環(huán)的循環(huán)條件是2N-1，至于第二個for循環(huán)，就是要保證2點，第一i與j的差距從小到大遍歷，第二i與j的差距不超過N，因為你現(xiàn)在數(shù)組的長度是2N，但是珠子仍舊只有N顆，防止計算f(1,2N-1)這種無意義的值。