动态DP

FJ_00460 · 2025-02-09 19:28:20 · 算法·理论

动态动态规划

四边形不等式的优化

for(int i = 1 ; i <= n ; i ++){
    dp[i][i] = 0; //s[][]的初始值
    s[i][i] = i;
} 
for(int len = 2; len <= n ; len ++)
    for(int i = 1 ; i <= n - len + 1; i ++){
        int j = i + len - 1;
        for(k = s[i][j - 1]; k <= s[i + 1][j]; k ++){ //缩小循环范围
            if(dp[i][j] > dp[i][k] + dp[k + 1][j] + w[i][j]){//是否更优
                dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j];
                s[i][j] = k;//更新最佳分割点
            }
        }
    }

时间复杂度: 比O(n^2)小很多