最大值为什么在两个端点上取到呢
查看原帖
最大值为什么在两个端点上取到呢
419567
izlyforever楼主2021/2/5 00:09
dp[i][j]=max⁡i≤k<jdp[i][k]+dp[k+1][j]+w(i,j)dp[i][j] = \max_{i \leq k < j} dp[i][k] + dp[k + 1][j] + w(i, j)

其中 w(i,j)=a[j]−a[i−1]w(i, j) = a[j] - a[i - 1]，aa 严格单调递增（从而满足区间单调性和四边形恒等式），dp[i][i]=0dp[i][i] = 0。然后如何证明

dp[i][j]=max⁡(dp[i][j−1],dp[i+1][j])+w(i,j)dp[i][j] = \max(dp[i][j - 1], dp[i + 1][j]) + w(i, j)
2021/2/5 00:09