动态规划针对特定问题求解的例子有很多, 本文将从普适的情况来系统地定义及分析动态规划. 我们首先提出两个问题. 

Problem 1.1
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列不能包含字符串 C 作为它的子序列. 

Problem 2.1
试分析动态规划问题的空间复杂度.

第一个问题是一个经典问题"最长公共子序列" (Longest Common Subsequence, LCS) 的一个扩展. 注意子序列 (subsequence) 和子串 (substring) 的区别在于, 子串指原字符串中连续出现的若干字符, 而子序列则不要求在原字符串中出现的字符连续 (保证次序即可). 举个例子, "hlo" 是字符串 "hello" 的子序列而不是子串, 因为它在 "hello" 中不连续.

第二个问题更系统一些. 仅仅用针对特殊动态规划问题的求解模型是回答不清楚这个问题的. 为了把它解释清楚, 我会从半环开始来定义动态规划问题的适用范围, 从而揭示出动态规划问题的本质, 并通过更底层的代数结构来解释动态规划的空间复杂度.

我们先提出一个问题.

Problem 1.1
有两个 n 行 n 列的矩阵 A, B. 定义两种运算, 第一种是计算 A 和 A 相乘的值, 第二种是计算 A 和 B 相乘的值. 求比较两种运算的复杂度.

即便我们不知道计算机是怎么实现矩阵乘法, 我们仍可以看到, 第一种运算是第二种运算的一个子问题, 因此复杂度不会高于后者. 

于是我们尝试计算一下矩阵的复杂度. 假定 A = [a[i][j]] 和 B = [b[i][j]] 的乘积是 C = [c[i][j]], 那么c[i][j]的值如下可求. 直观地讲, 计算出一个c[i][j]需要把 n 对 a[i][k] 和 b[k][j] 相乘, 因此需要至少 O(n) 的复杂度; 计算出整个 C 需要至少 O(n^3) 的复杂度.

事实上我们可以采用一些巧妙的办法对矩阵乘法进行提速. 而传统运算中也有一些很经典的提速算法, 最典型的是快速幂. 我们将介绍一下运算操作的原理和一些提速的方法, 进而剖析一下矩阵复杂度的问题, 进而分析problem 1.1中蕴含的奥秘.

前几天碰到一道被"全新包装"的经典问题:

Problem 1.1
给定2n+2个数, 其中2n个数两两相同, 另外两个数都是唯一的. 请设计一个算法找出这两个数, 要求使用的空间尽可能的少. 

从一道面试题的角度来讲, 这个问题被包装的很巧妙. 如果应聘者临时抱佛脚地翻阅一遍经典算法题的话, 则很难找到与这个问题的关联; 对于面试官来说, 就更容易淘汰实力不足的应聘者.

本文将从”位“这一个基础的知识模块谈起, 提及编码和位运算, 进而给出这道题目, 以及一系列经典问题的解法.

大学留下的东西很少.

这篇文章写与2011年8月15日, 也就是我的生日之前. 基本上算是大学期间唯一过得去的作品了. 噢, 对了, 另一篇"过得去的作品"是一个叫做"关于信科大一下选课的一二事（by 阿笨兔）"的东西.

我之前的一个博客, 阿笨兔的ACM小屋, 里面有60余篇当时在北大ACM集训队撰写的解题报告. 虽然报告的整体质量不高, 不过也有些内容.

原博客地址请见,

http://blog.sina.com.cn/abentu0101