求解问题最优方案 – 动态规划基础

动态规划

回溯穷举所有分支，主要用于罗列出所有满足条件的具体方案；而动态规划是在回溯的基础上，每一阶段的决策中选择最优的一个，主要用于给出确定的一个最优解，即动态规划用于求解 可选元素在一定条件下的最优方案 问题。其具体步骤是表示问题、找到问题之间的递推关系、确定递推边界、根据递推方向确定元素计算顺序、根据元素计算顺序复用存储空间减少消耗。

以0-1背包问题为例讲明回溯到动态规划的演变和改进，先用回溯实现

public static void main(String[] args) {
    int value = backtracking(n - 1, capacity);
}

public static int backtracking(int i, int c) {
    if(i == -1) return 0;
    if(c < w[i]) return dfs(i - 1, c);
    return Math.max(backtracking(i - 1, c - w[i]) + v[i], backtracking(i - 1, c));
}

我们注意到回溯计算了大量的重复子问题，一个朴素的想法是将已计算过的结果存储重复利用，我们称为记忆化搜索。

能否进一步优化呢？我们注意到子问题的计算顺序后，可以按照拓扑将每种状态只计算一次，后续所有状态均需基于已计算状态推导，用迭代改写进一步减少递归调用的消耗

public int (int n, int capacity) {
    int dp[n + 1][capacity + 1];

    for(int i = 1; i <= n; i++)
        for(int c = 1; c <= capacity; c++)
            if(c >= w[i]) dp[i][c] = max(dp[i - 1][c - w[i]] + v[i], dp[i - 1][c]);
            else dp[i][c] = dp[i - 1][c];

    return dp[n][capacity];
}

在二维数组情况下，可以通过倒推记录方案

int c = capacity;
for(int i = n; i >= 1; i--) {
    if(dp[i][c] != dp[i - 1][c]) {
        System.out.printf("%d 被选择\n", i);
        i--;
        c -= w[i];
    }
}

还能优化吗？我们注意到状态转移方程的转移方向单一，且与行或列平行，可 仅用一行或一列数据迭代 以减少空间使用，注意防止计算过程中子问题被覆盖，因而要考虑状态计算顺序正序、逆序。此情况下不能再倒推记录方案

public int (int n, int capacity) {
    int n = w.size();
    int dp[capacity + 1];

    for(int i = 1; i <= n; i++)
        for(int c = capacity; c >= w[i]; c--)
            dp[c] = max(dp[c - w[i]] + v[i], dp[c]);

    return dp[capacity];
}

应用案例

最长递增子序列

int LIS(vector<int> x)
{
    int dp[x.size()];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    int ans = 1;

    for (int i = 1; i < x.size(); i++)
    {
        int maxj = 0;
        for (int j = 0; j < i; j++)
            if (x[i] > x[j])
                maxj = max(maxj, dp[j]);

        dp[i] = maxj + 1;
        ans = max(ans, dp[i]);
    }

    return ans;
}

最长公共子序列

    int LCS(string x, string y)
    {
        int dp[x.length() + 1][y.length() + 1];
        memset(dp, 0, sizeof(dp));

        for (int i = 1; i <= x.length(); i++)
            for (int j = 1; j <= y.length(); j++)
                if (x[i - 1] == y[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

        return dp[x.length()][y.length()];
    }

编辑距离

■ 问题定义：dp[i][j]表示A[1..i]B[1..j]的编辑距离
■ 转移方程：A[i] = B[j], dp[i][j] = dp[i-1][j-1]
           A[i] ≠ B[j], dp[i][j] = dp[i-1][j] + 1，A[i-1]加一个字符
           A[i] ≠ B[j], dp[i][j] = dp[i][j-1] + 1，B[j-1]加一个字符，等效于A[i]删一个字符
           A[i] ≠ B[j], dp[i][j] = dp[i-1][j-1] + 1，A[i]替换一个字符
■ 边界条件：空串到A[1...i]的编辑距离为i

public int minDistance(String word1, String word2) {
    int m = word1.length() + 1;
    int n = word2.length() + 1;
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++)
        dp[i][0] = i;

    for (int i = 1; i < n; i++)
        dp[0][i] = i;

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1))
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) + 1);
            else
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
        }
    }

    return dp[m - 1][n - 1];
}

最长回文子序列

int LPS(string s) {
    int n = s.size();
    int dp[n][n];
    memset(dp, 0, sizeof(dp));

    for (int j = 0; j < n; j++) {
        dp[j][j] = 1;
        for (int i = j - 1; i >= 0; i--)
        {
            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]);
        }
    }

    return dp[0][n - 1];
}

最长回文子串

■ 问题定义
        dp[i][j]表示s[i..j]是否是回文子串
■ 状态转移
        s[i] == s[j] dp[i][j] = dp[i+1][j-1];
        s[i] != s[j] dp[i][j] = false;
■ 边界条件
        i == j dp[i][i] = true; 单字符为回文串
        i > j  dp[i][j] = true; 空串为回文串
■ 转移方向
        依赖左下角状态，计算时应从左至右竖向遍历
■ 滚动优化
        可优化为为一维列数组的滚动

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";

        boolean[] dp = new boolean[s.length()];
        int maxLen = 1, maxLeft = 0, maxRight = 0;

        for (int i = 0; i < s.length(); i++)
            dp[i] = true;

        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (dp[i] = dp[i + 1]) {
                        int curLen = j - i + 1;
                        if (curLen > maxLen) {
                            maxLen = curLen;
                            maxLeft = i;
                            maxRight = j;
                        }
                    }
                } else dp[i] = false;
            }
        }

        return s.substring(maxLeft, maxRight + 1);
    }
}