写在前面
动态规划针对特定问题求解的例子有很多, 本文将从普适的情况来系统地定义及分析动态规划. 我们首先提出两个问题.
Problem 1.1
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列不能包含字符串 C 作为它的子序列.
Problem 2.1
试分析动态规划问题的空间复杂度.
第一个问题是一个经典问题"最长公共子序列" (Longest Common Subsequence, LCS) 的一个扩展. 注意子序列 (subsequence) 和子串 (substring) 的区别在于, 子串指原字符串中连续出现的若干字符, 而子序列则不要求在原字符串中出现的字符连续 (保证次序即可). 举个例子, "hlo" 是字符串 "hello" 的子序列而不是子串, 因为它在 "hello" 中不连续.
第二个问题更系统一些. 仅仅用针对特殊动态规划问题的求解模型是回答不清楚这个问题的. 为了把它解释清楚, 我会从半环开始来定义动态规划问题的适用范围, 从而揭示出动态规划问题的本质, 并通过更底层的代数结构来解释动态规划的空间复杂度.
Problem 1.1
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列不能包含字符串 C 作为它的子序列.
Problem 2.1
试分析动态规划问题的空间复杂度.
第一个问题是一个经典问题"最长公共子序列" (Longest Common Subsequence, LCS) 的一个扩展. 注意子序列 (subsequence) 和子串 (substring) 的区别在于, 子串指原字符串中连续出现的若干字符, 而子序列则不要求在原字符串中出现的字符连续 (保证次序即可). 举个例子, "hlo" 是字符串 "hello" 的子序列而不是子串, 因为它在 "hello" 中不连续.
第二个问题更系统一些. 仅仅用针对特殊动态规划问题的求解模型是回答不清楚这个问题的. 为了把它解释清楚, 我会从半环开始来定义动态规划问题的适用范围, 从而揭示出动态规划问题的本质, 并通过更底层的代数结构来解释动态规划的空间复杂度.