http://acm.hdu.edu.cn/showproblem.php?pid=1024
題意就是求你n個數字m段和的最大值
用動态規劃求dp[n][m] 表示用前m個數劃分為n塊的最大和
轉移方程為 dp[n][m]=max(dp[n][m-1]+a[m],max(dp[n-1][t])+a[m]),其中dp[n][m-1]+a[m]表示第m個在前i塊中 後面表示的是在自己獨立變成一個塊（1<=t<=m-1）
那麼問題來了如果 用這種方法 複雜度為（n^3）是以我們要化簡一下，求max(dp[n-1][t])的時候重複求了一些過程，是以隻需要改成 設一個變量M 表示前1到m-1的最大值 M=max(M,dp[i-1][j-1]);
但是空間上不夠，是以用一個滾動數組 dp[2][MAN]；在求M的用到了i-1;
完整代碼：
View Code