855学习记录算法动态规划$Day$-$6$——炎泽汐$de$ Blog

游船租赁

---

//游船租赁
int YachtLeasing(vector<vector<int> >& r, int a, int b){
    int n = r.size();
    int dp[n + 1][n + 1];
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            dp[i][j] = r[i][j];
        }
    }
	
    for(int len = 3; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            int l = i, r = i + len - 1;
            for(int k = l + 1, k < r; k++){
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r]);
            }
        }
    }
	
    if(b > a){
        swap(a, b);
    }
	
    return dp[a][b];
}

矩阵链乘法

---

//矩阵链乘法
int dp[MaxN + 1][MaxN + 1];
int s[MaxN + 1][MaxN + 1];
int MatrixChainMultiplication(vector<int>& p){
    int n = p.size() - 1;
    memset(dp, 0, sizeof(dp));
    memset(s, 0, sizeof(s));
	
    for(int len = 2; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            int l = i, r = i + len - 1;
            dp[l][r] = dp[l + 1][r] + p[i - 1] * p[i] * p[j];
            s[i][j] = i;
            for(int k = l + 1, k < r; k++){
            	int t = dp[l][k] + dp[k + 1][r] + p[l - 1] * p[k] * p[j];
                if(t < dp[l][k]){
                    dp[l][k] = t;
                    s[l][k] = k;
                }
            }
        }
    }
	
    if(b > a){
        swap(a, b);
    }
	
    GetSolve(1, n);
	
    return dp[1][n];
}

void GetSolve(int i, int j){
    if(i == j){
        cout << "A[" << i << "]";
        return ;
    }
	
    cout << "(";
    GetSolve(i, s[i][j]);
    GetSolve(s[i][j] + 1, j);
    cout << ")";
}

最优三角剖分

---

//最优三角剖分
double dp[MaxN + 1][MaxN + 1];
int s[MaxN + 1][MaxN + 1];
double OptimalTriangulation(vector<vector<int> >& g){
    int n = p.size();
    memset(dp, 0, sizeof(dp));
    memset(s, 0, sizeof(s));
	
    for(int len = 2; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            int l = i, r = i + len - 1;
            dp[l][r] = dp[l + 1][r] + g[l - 1][l] + g[l][r] + g[l - 1][r];
            s[i][j] = i;
            for(int k = l + 1, k < r; k++){
                double t = dp[l][k] + dp[k + 1][r] + g[l - 1][k] + g[k][r] + g[l - 1][r];
                if(t < dp[l][k]){
                    dp[l][k] = t;
                    s[l][k] = k;
                }
            }
        }
    }
	
    GetSolve(1, n);
	
    return dp[1][n];
}

void GetSolve(int i, int j){
    if(i == j){
        return ;
    }
    
    if(s[i][j] > i){
        cout << "{v_{" << i - 1 << "},v_{" << s[i][j] << "}}" << endl;
    }
    if(j > s[i][j] + 1){
        cout << "{v_{" << s[i][j] << "},v_{" << j << "}}" << endl;
    }
    GetSolve(i, s[i][j]);
    GetSolve(s[i][j] + 1, j);
}