本题与普通区间dp有一些区别，下面我悉数道来

  1. 首先决策：每次一次的决策（往左或者往右走），发现其一定是一个连续区间关闭；
  2. 关于本题与常规区间dp的区别：完成一个区间时最优解一定停在区间两端，而从小区间推至大区间的过程，要考虑距离成本 故小区间所停在的左右端点不同对后续造成影响，故要将其纳入状态；
  3. 状态分析 由上述分析易知dp[i][j][0/1] 0表示在左端，1表示在右端
  4. 转移方程
dp[i][j][0]=min(dp[i+1][j][0]+(d[i+1]-d[i])*(sum[n]-sum[j]+sum[i]),dp[i+1][j][1]+(d[j]-d[i])*(sum[n]-sum[j]+sum[i]));

dp[i][j][1]=min(dp[i][j-1][1]+(d[j]-d[j-1])*(sum[n]-sum[j-1]+sum[i-1]),dp[i][j-1][0]+(d[j]-d[i])*(sum[n]-sum[j-1]+sum[i-1]));
  1. 这题的循环有两种写法 可以思考一下原因 方一：枚举区间长度（从小到大）
  2. 方二：枚举左右两端点
for(int i=n;i>=1;i--){
            for(int j=i+1;j<=n;j++){
                //int j = i+len-1;
                dp[i][j][0]=min(dp[i+1][j][0]+(d[i+1]-d[i])*(sum[n]-sum[j]+sum[i]),dp[i+1][j][1]+(d[j]-d[i])*(sum[n]-sum[j]+sum[i]));
                dp[i][j][1]=min(dp[i][j-1][1]+(d[j]-d[j-1])*(sum[n]-sum[j-1]+sum[i-1]),dp[i][j-1][0]+(d[j]-d[i])*(sum[n]-sum[j-1]+sum[i-1]));
            }
        }

思考这种转移的成立性：机理也是从小区间往大区间转移 对比石子合并：石子合并因一大区间可由其任意包含的两个小区间合并，并不需要是靠近的，故要找分界点，多一个循环k 故需要先求出所有小区间的最优解才可以求相应大区间 而此题并不需要求出所有小区间的解，只需要几个