注释：

p(i, j) 表示整条路上除了 i 到 j 以外路灯的功率。

dp[i][j][0/1]表示关完 i 到 j 的路灯，老张站在左/右端点，所耗费的最小功率

一开始写的时候想到了四个状态。

对于dp[i][j][0]

已经关掉了 i + 1 到 j

dp[i + 1][j][0] + p(i + 1, j) 从 i + 1 走到 i

dp[i + 1][j][1] + (j - i) * p(i + 1, j) 从 j 走到 i

已经关掉了 i 到 j - 1

dp[i][j - 1][0] + (j - i) * p(i, j - 1) + (j - i) * p(i, j) 从 i 走到 j， 再走到 i

dp[i][j - 1][1] + p(i, j - 1) + (j - i) * p(i, j) 从 j - 1 走到 j， 再走到 i

---

但是，所有题解都没有考虑后两种情况，虽然看起来走了很多路程，但是怎么证明这两种走法一定劣于前两种呢？

求教