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

线性$DP$：数字三角形

---

//线性 DP：数字三角形
int Triangle(int n, int a[][100]){
    int DP[n + 1][n + 1];
    memset(DP, -0x3f, sizeof(DP));
    DP[1][1] = a[1][1];
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            DP[i][j] = max(DP[i - 1][j - 1] + a[i][j], DP[i - 1][j] + a[i][j]);
        }
    }
    int res = 0xc0c0c0c0;
    for(int i = 1; i <= n; i++){
        res = max(res, DP[n][i]);
    }
    return res;
}

线性$DP$：最长上升子序列

---

//线性 DP：最长上升子序列
int LongestIncreasingSubsequence(int n, int a[]){
    int DP[n + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        DP[i] = 1;
        for(int j = 1; j < i; j++){
            if (a[j] < a[i]){
                DP[i] = max(DP[i], DP[j] + 1);
            };
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
            res = max(res, DP[i]);
    }
    return res;
}

//线性 DP：最长不下降子序列(二分优化)
int LongestIncreasingSubsequence(int n, int a[]){
    int DP[n + 1], l[n + 1];
    memset(DP, 0, sizeof(DP));
    memset(l, 0, sizeof(l));
	
    int ans = 1;
    DP[1] = 1;
    l[1] = a[1];
	
    for(int i = 2; i <= n; i++){
        DP[i] = 1;
        if(a[i] <= l[ans1]){
            dp[i] = ++ans;
        }else{
            int j = upper_bound(l + 1, l + ans1 + 1, a[i], greater<int>()) - l;
            dp[i] = j;
        }
        l[dp[i]] = a[i];
    }

    return ans;
}

线性$DP$：最长公共子序列

---

//线性 DP：最长公共子序列
int LongestCommonSubsequence(int n, int m, char a[], char b[]){
    int DP[n + 1][m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            if(a[i] == b[j]){
                DP[i][j] = max(DP[i][j], DP[i - 1][j - 1] + 1);
            }
        }
    }
	
    return DP[n][m];
}

区间$DP$：石子合并

---

//区间 DP：石子合并
int StoneMerging(int n, int s[]){
    int DP[n + 1][n + 1];
    for(int i = 1; i <= n; i++){
        s[i] += s[i - 1];
    }
    memset(DP, 0, sizeof(DP));
	
    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] = 0x3f3f3f3f;
            for(int k = l, k < r; k++){
                DP[l][r] = min(DP[l][r], DP[l][k] + DP[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
	
    return DP[1][n];
}