怕黑路人

文章
5
资源
0
加入时间
2年10月21天

斜率优化dp

很好的总结 很好的专题斜率优化dp基本上都是可以化到 dp[i]=min(dp[j]+cost(j+1,i)) 这样的形式,二维的就是dp[i][m]=min(dp[j][m-1]+cost(j+1,i)); 概括一下: 1.假设第dp[i]dp[i]两个决策点j,k(j<k)j,k(j<k),且kk的决策要比jj好 接下来证明对于dp[i+1]dp[i+1]及其后面的决策都满足kk的决策要