动态规划总结（一）

子序列问题的两种思路

一维dp数组

int n = array.length;
int[] dp = new int[n];

for(int i = 1; i < n; i++) {
    for(int j = 0; j < i; j++) {
        dp[i] = max(dp[i], dp[j] + ...) // min(dp[i], dp[j] + ...)
    }
}

最长递增子序列

二维dp数组

int n = array.length;
int[][] dp = new dp[n][n];

for(int i = 1; i < n; i++) {
    for(int j = 0; j < i; j++) {
        if(arr[i] == arr[j]) {
            dp[i][j] = dp[i][j] + ...
        }
        else {
            dp[i][j] = max(...) // min(...)
        }
        
    }
}

最长回文子序列

状态压缩

状态转移方程的主要代码

// base case 
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++) {
    dp[i][i] = 1;
}

for(int i = n - 1; i >= 0; i--) {
    for(int j = i + 1; j < n; j++) {
        if(s[i] == s[j]) {
            dp[i][j] = dp[i+1][j-1] + 2;
        }
        else {
            dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }
}

进行状态压缩以后的代码

// base case
vector<int> dp(n, 1);

for(int i = n - 1; i >= 0; i--) {
    // 储存 dp[i+1][j-1] 的变量
    int pre = 0;
    for(int j = i + 1; j < n; j++) {
        int temp = dp[j];
        if(s[i] == s[j]) {
            // dp[i][j] = dp[i+1][j-1] + 2
            dp[j] = temp + 2;
        }
        else {
            dp[j] = max(dp[j], dp[j-1]);
        }
        // 下一轮循环中 pre = dp[i+1][j-1]
        pre = temp;
    }
}

continue updating