Dynamic Programming

动态规划

建议观看 MIT 算法导论-动态规划中的课程。

适用于动态规划的问题，需要满足最优子结构和无后效性，动态规划的求解过程，在于找到状态转移方程，进行自底向上的求解。

例题

爬楼梯问题 LeetCode 70

经典的动态规划问题之一，容易找到其状态转移方程为 dp[i] = dp[i-1] + dp[i-2]，从基础的 1 和 2 个台阶两个状态开始，自底向上求解：

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }

    int* dp = new int[n+1]();
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

从上面的代码中看到，dp[i] 只依赖 dp[i-1] 和 dp[i-2]，因此可以将代码简化：

int climbStairs(int n) {
    int f0 = 1, f1 = 1, i, f2;
    for (i=2; i<=n; i++) {
        f2 = f0 + f1;
        f0 = f1;
        f1 = f2;
    }
    return f1;
}

容易看出其实结果就是 fibonacci 数列的第 n 项。

连续子数组的最大和 LeetCode 53

用 dp[n] 表示元素 n 作为末尾的连续序列的最大和，容易想到状态转移方程为dp[n] = max(dp[n-1] + num[n], num[n])，从第 1 个元素开始，自顶向上求解：

int maxSubArray(vector<int>& nums) {
    int* dp = new int[nums.size()]();

    dp[0] = nums[0];
    int result = dp[0];

    for (int i = 1; i < nums.size(); i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        result = max(result, dp[i]);
    }

    return result;
}

类似前一个问题，这个问题当中，求解 dp[i] 只依赖 dp[i-1]，因此可以使用变量来存储，简化代码：

int maxSubArray(int A[], int n) {
    int result = INT_MIN;
    int f = 0;
    for (int i=0; i < n; i++) {
        f = max(f + A[i], A[i]);
        result = max(result, f);
    }
    return result;
}

House Robber LeetCode 198

对于一个房子，有抢和不抢两种选择，容易得到状态转移方程 dp[i+1] = max(dp[i-1] + nums[i], dp[i])，示例代码如下：

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }

    vector<int> dp = vector<int>(n + 1);

    dp[0] = 0;
    dp[1] = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        int v = nums[i];
        dp[i+1] = max(dp[i-1] + v, dp[i]);
    }

    return dp[n];
}

同样的，可以使用两个变量简化代码：

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }

    int prev1 = 0;
    int prev2 = 0;

    for (int i = 0; i < nums.size(); i++) {
        int v = nums[i];
        int temp = prev1;
        prev1 = max(prev2 + v, prev1);
        prev2 = temp;
    }

    return prev1;
}

最长回文子串 LeetCode 5

用 dp[i][j] 表示子串 i 到 j 是否是回文，使用动态规划求解：

string longestPalindrome(string s) {
	int m = s.size();
	if (m == 0) {
		return "";
	}
	vector<vector<int>> dp(m, vector<int>(m, 0));
	int start = 0;
	int length = 1;

	for (int i = 0; i < m; i++) {
        // 单个字符属于回文，例如 abcd
		dp[i][i] = 1;

        // 连续两个字符相同属于回文，例如 abb
		if (i < m - 1) {
			if (s[i] == s[i + 1]) {
				dp[i][i + 1] = 1;
                start = i;
				length = 2;
			}
		}
	}

	for (int len = 2; len <= m; len++) {
		for (int i = 0; i < m - len; i++) {
			int j = i + len;
            // 扩展长度
			if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
				dp[i][j] = 1;

				if (j - i + 1 > length) {
                    start = i;
					length = j - i + 1;
				}
			}
		}
	}

	return s.substr(start, length);
}

最小编辑距离 LeetCode 72

用 dp[i][j] 表示从 word[0..i) 转换到 word[0..j) 的最小操作，使用动态规划求解：

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 全部删除，操作数量为 i
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }

    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 末尾字符相同，不需要编辑
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 末尾字符不同，三种编辑情况，取最小值
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
    }

    return dp[m][n];
}