[今天我们思考13]两道经典算法题的几种思维方法
pongba
对两道经典的算法题的思考过程作了一个总结，其中每道题目除了一种思维方法是做的时候实际用的之外，另外的是做完之后通过合情推理认为如果回到当时也是可行的思路。总结出来，为了提醒自己思路的全面性。我认为练习解题的最重要意义在于获得一般性的解题思维习惯，因为它才是跨问题的。因此在练习的过程中我总是不断反省自己的思维活动过程，这有两个作用，一是最快最有效地反省总结，从而最快地养成好习惯。二是通过考察自己的思维过程能够防止落入思路陷阱。
从获得一般性的解题思维习惯的目的来看，每道没做过的题目都有极大的价值，因为我们咀嚼的不是题目，而是解题的思维本身。
欢迎大家补充自己的！:)
问题1描述：名人问题
一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。
思维方法一：特例。考虑两个人。发现，如果A、B如果互相认识，或互相不认识，则他们都不可能是名人。如果其中之一认识另一个（不失一般性我们令A认识B），则A被淘汰。
思维方法二：倒推。假设名人已经出现，考虑名人的定义，一个名人P是指满足如下两个条件的人：
- 任取一个人Q，Q认识P。
- 任取一个人Q，P不认识Q。
接着，出于对"哪些人不符合名人的标准从而可以在我们搜索解空间的时候直接淘汰掉呢？"这个问题的询问。我们考察以上条件的反面。即"如果__则P不是名人"这个填空：
- 存在一个人Q，Q不认识P。
或
- 存在一个人Q，P认识Q。
根据这两个条件，我们实际上就可以优化穷举式的搜索，因为当比较两个人P1和P2的关系的时候，我们发现利用上面两个规则，其中最多只能有一个人具有"名人潜质"，因为根据以上规则，不管这两人之间出现认识还是不认识关系，总有一个人要被刷掉。
思维方法三：联想。联想的可能性有
- 这 是一个涉及n的问题，尝试用归纳法，即考虑其子问题。如何定义子问题？两个明显的办法：1，二分为两个n/2规模的子问题。一个名人必然是这两个子问题里 面的名人，所以问题归约为求解两个子问题，并在最后一个环节合并这两个子问题的解。2，考虑n-1阶的子问题。一个名人必然是n-1阶子问题中的名人，问 题被归约为求解n-1阶子问题，然后其结果——n-1阶名人与最后一个人的关系进行比较。最后，不管采用两种归纳法中的哪一个，最后一步优化都是一样的， 即将递归方案转化为迭代方案。
- 这是一个涉及n的问题，直接联想到递归算法，于是试图去凑一个递归的程序，结果同上面的第2种方案一样。
- 由于是在n个人中"争"出一个名人，因此联想到竞赛，试着往传统竞赛算法上凑，即一个个的比并淘汰的方案，并因此发现内中的淘汰规则。
- etc. （有人补充吗？）
问题2描述：和最小连续子序列问题
有N个数，其中有正有负，求出其中和最小的连续子序列。（连续子序列就是a[i]~a[j]所有连续元素形成的序列，其中i，j任取）
思维方法一： 倒推。假设最小和子序列已经找到，我们试着去尽量挖掘这个最小和子序列的性质，每个性质都有助于另我们更"智能地"在解空间中进行搜索。我们不难发现，这 个假想的最小和子序列的两端元素必然是负的，否则我们可以削掉它们求得一个更小和的子序列。再进一步我们会发现，事实上这个最小和子序列从任意一段算起的 一个前缀/后缀的和必然也是负的，否则我们也可以将其削掉来求得一个更小和的子序列。此外，与这个最小和子序列两端紧邻着的任意一段区间的和必然是正的， 否则我们必然可以将其添加到我们假设的最小和序列上，以求得一个更小和的子序列。一旦挖掘出了以上三个被蕴含在结论中的条件，我们就可以更为智能地搜索解 空间了。
思维方法二：这是一个涉及n的问题，试着考察其子问题。我们能将问题降到n-1阶吗？n阶 问题里面的最小和子序列与n-1阶里面的最小和子序列有什么关联吗？如果n阶问题里面的最小和子序列不含有最后一个元素，那么它肯定同样也是n-1阶问题 中的最小和子序列。这种情况下我们就完全将问题降到了n-1阶。但如果它包含最后一个元素，那么一个自然的问题就是，n-1阶问题中的最小和子序列含在n 阶最小子序列切掉最后一个元素之后剩下的那个序列内吗？如果是的话，这种情况下问题也可以归约为n-1阶，也就是说只有n-1阶中的最小和序列才具有潜质 成长为n阶的最小和序列。然而，第二种情况下的答案却是否定的（试着找一个反例）。所以看上去这条路行不通。一般来说，一条路行不通之后，首先要做的就是 反省一下思路，看看到底什么地方出了什么问题，也许有可能修修补补之后就能够得到正确答案——想一想，我们刚才是在试着将问题降到n-1阶。那么，为什么 一定要是n-1阶呢？譬如二分法就是试图将问题降到两个n/2阶子问题。为什么这里将问题降到n-1阶是不奏效的？因为这样的降阶无法保证我们solve 了n-1阶的子问题之后能够根据它的解来构造n阶问题的解。再仔细看看我们的方法，我们也许会发现，问题实质上出在最小和子序列可能会从n-1阶跨越到n 阶，换句话来说，问题的可能解会跨越两个子问题，这样的子问题分解得到的是不完全的子问题，我们除了需要solve两个子问题之外，还需要考虑跨越这两个 子问题的潜在解，这可是个麻烦事儿。最好的子问题分解是只需要直接solve掉子问题就结了，举个例子，我们熟悉的快速排序，快速排序将一个区间根据一个 中轴元素分解为两个区间之后，就将问题分解为了两个子问题，然后就只需要solve这两个子问题（将这两个区间排序），就直接了结了。它的两个子问题是完 全分离的，我们不必担心任何左区间内的元素和右区间内的元素会出现乱序的情况。那么，我们的这个问题，关键就在于应该也将它分解为两个完全子问题，我们设 想有某种手法，能够将我们n个数分解为两段，其中要想求全局的最小和子序列，我们只需要对这两段分别求其中的最小和子序列，然后看看哪个小即可。我们无需 考察跨越这两个区间的子序列。这样一来我们就可以非常省心的将问题一步步分解为完全的子问题了。然而，到底怎样才能分解出这样的两个区段来呢？看看我们的 未知数是什么。我们的未知数是要寻找这样的切分。但我们现在很茫然，n-1后面切一刀不行，二分法也不行，到底怎么切呢？看来这样盲目尝试是不行的。试试 倒推吧。我们假设这样的切割已经出现了，它满足"最小和序列肯定不会跨越其切割边界"这个条件，即任取一个跨越其切割边界的子序列，都必然不是最小和序 列。那么要怎样才能让一个序列不是最小和序列呢？想想上面思维方法一里面推导出的结果，最小和序列的任意前缀后缀序列必然和为负；且两端向外扩展的序列和 必然为正。所以，要想让一个序列和不是最小，我们只要让情况不满足这两个条件即可。基于这个条件，细心耐心一点很快就会推导出这个切割所需满足的性质了。
思维方法三：直接联想到动态规划。然后往动态规划上硬套。硬套的过程中必然会受挫（看了下面的做法你就 知道为什么不是简单的动态规划了），也许经过一定的试错，会联想到Introduction to Algorithms里面那个关于排课的问题，从而想到将区间按照结尾元素的不同来分类：（这个思路是网上抄来的，关键是"考虑以某个a[x]终止的所有 子序列"这一步很是摸不着头绪。有谁能够提供这个做法背后的思维过程吗？）
设 f[x] 为以 a[x] 终止且包含 a[x] 的最小序列的和，有：
f[1] = a[1];
f[x+1] = f[x] < 0 ? f[x] + a[x+1] : a[x+1]
那么最小子序列的和就是 f[1] .. f[n] 中最小的一个。
参考：
5. 练习，练习
本质上，练习并不产生新能力。然而练习最重要的一个作用就是将外显记忆转化为内隐记忆。用大白话来说就是将平时需要用脑子去想（参与）的东西转化为内在的习惯。譬如我们一开始学骑自行车的时候需要不断提醒自己注意平衡，但随着不断的联系，这种技能就内化成了所谓的程序式记忆（内隐记忆的一种），从而就算你一边骑车一边进行解题这样需要消耗大量脑力的活动，也无需担心失去平衡（不过撞树是完全可能的，但那是另一回事）。
同样，对于解题中的思维方法来说，不断练习这些思维方法就能做到无意识间就能运用自如，大大降低了意识的负担和加快了解题速度。
不过，并非所有的练习方法都是等效的，有些练习方法肯定要比另一些更有效率。譬如就解题来说，解题是一项涉及到人类 最高级思维机制的活动，其中尤其是推理（归纳和演绎）和联想。而后者中又尤数联想是最麻烦的，前面提到，绝大多数时候启发式方法实质上都是在为联想服务 ——为了能像晃筛子那样把你脑袋里那个关键的相关知识抖落出来。并且，为了方便以后能够联想，在当初吸收知识的时候就需要做最恰当的加工才行，譬如前面提 到的"抽象"加工，除此之外还有将知识与既有的知识框架整合，建立最多的思维连接点（或者说"钩子"）。对于知识的深浅加工所带来的影响，《找寻逝去的自我》里 面有精彩的介绍（里面也提到了提取线索对回忆的影响——从该意义上来说运用启发式思维方法来辅助联想，其实就是进行策略性记忆提取的过程）。最后，人类的 无意识思维天生有着各种各样的坏习惯，譬如前面提到的范畴陷阱就是创新思维的杀手，譬如根据表面相似性进行类比也是知识转移的一大障碍。更遑论各种各样的思维捷径了 （我们平常进行的绝大多数思考和决策，都是通过认知捷径来进行的）。所以说，如果任由我们天生的思维方式发展，也许永远都避不开无意识中的那些陷阱，好在 我们除了无意识之外还多出了一层监督机制——意识。通过不断反省思维本身，时时纠正不正确的思考方式，我们就能够对其进行淬炼，最终养成良好的思维习惯。 反之被动的练习虽然也能熟能生巧，但势必花的时间更多，而且对于涉及复杂的思维机制的解题活动来说，远远不是通过钱眼往油壶里面倒油这样简单的活动所能类 比的，倒油不像思维活动那样有形形色色的陷阱，倒油不需要联想和推理，倒油甚至几乎完全不需要意识的辅助性参与，除了集中注意力（而解题活动就算对于极其 熟练的人来说也不断需要大量的意识参与）。所以对于前者，良好的思维习惯至关重要，而反省加上运用正确的思维方法则是最终养成良好思维习惯的途径。
练习还有另外一个很重要的作用，就是增加领域知识（关于知识在问题解决中的作用，前面已经提到过）。我们看到很多 人，拿到一道题目立即脑子里就反应出解法，这个反应快到他自己都不能意识到背后有什么逻辑。这是因为既有的知识（我们常说的"无他，实在是题做得太多 了"）起到了极大的作用，通过对题目中几个关键元素或结构的感知，大脑中的相关知识迅速被自动提取出来。而对于知道但不熟悉相应知识（譬如很早我们就知道 归纳法，但是很久以后我们才真正能够做到面对任何一道可能用归纳法的题目就立即能够想到运用归纳法），或者干脆就不知道该知识的人来说，就需要通过启发法 来辅助联想或探索了。后者可以一定程度上代偿对知识的不够熟悉，但在一些时候知识的缺失则是致命的（参见上面第2点）。不过要注意的是，那种看到题目直接 反应出答案的或许也不是纯粹的好事，因为这样的解题过程严重依赖于既有知识，尤其是做过的类似的题目，其思维过程绝大部分运用的是联想或类比，而非演绎或 归纳。更重要的是，联想也分两种，被动联想和策略性联想（参考《找寻逝去的自我》），这里用的却是被动联想。所以，能直接反应出答案并不代表遇到真正新颖 的题目的时候的解决能力，后者由于不依赖于既有领域知识，就真正需要看一个人的思维能力和习惯究竟如何了。
============以后有更多的总结，还会继续review出新的版本。欢迎大家仍砖头:-)
--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba
windstorm
当然还可以回溯来解，但这样算法貌似就不是O(n)了吧？
2008/5/3 pongba <pon...@gmail.com>:
>
>
> 对两道经典的算法题的思考过程作了一个总结，其中每道题目除了一种思维方法是做的时候实际用的之外，另外的是做完之后通过合情推理认为如果回到当时也是可行的思路。总结出来，为了提醒自己思路的全面性。我认为练习解题的最重要意义在于获得一般性的解题思维习惯，因为它才是跨问题的。因此在练习的过程中我总是不断反省自己的思维活动过程，这有两个作用，一是最快最有效地反省总结，从而最快地养成好习惯。二是通过考察自己的思维过程能够防止落入思路陷阱。
>
> 从获得一般性的解题思维习惯的目的来看，每道没做过的题目都有极大的价值，因为我们咀嚼的不是题目，而是解题的思维本身。
>
>
> 欢迎大家补充自己的！:)
>
>
> 问题1描述：名人问题
>
>
> 一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。
>
> 思维方法一：特例。考虑两个人。发现，如果A、B如果互相认识，或互相不认识，则他们都不可能是名人。如果其中之一认识另一个（不失一般性我们令A认识B），则A被淘汰。
>
> 思维方法二：倒推。假设名人已经出现，考虑名人的定义，一个名人P是指满足如下两个条件的人：
> 任取一个人Q，Q认识P。
> 任取一个人Q，P不认识Q。
>
> 接着，出于对"哪些人不符合名人的标准从而可以在我们搜索解空间的时候直接淘汰掉呢？"这个问题的询问。我们考察以上条件的反面。即"如果__则P不是名人"这个填空：
> 存在一个人Q，Q不认识P。
>
> 或
> 存在一个人Q，P认识Q。
>
> 根据这两个条件，我们实际上就可以优化穷举式的搜索，因为当比较两个人P1和P2的关系的时候，我们发现利用上面两个规则，其中最多只能有一个人具有"名人潜质"，因为根据以上规则，不管这两人之间出现认识还是不认识关系，总有一个人要被刷掉。
>
> 思维方法三：联想。联想的可能性有
> 这 是一个涉及n的问题，尝试用归纳法，即考虑其子问题。如何定义子问题？两个明显的办法：1，二分为两个n/2规模的子问题。一个名人必然是这两个子问题里
> 面的名人，所以问题归约为求解两个子问题，并在最后一个环节合并这两个子问题的解。2，考虑n-1阶的子问题。一个名人必然是n-1阶子问题中的名人，问
> 题被归约为求解n-1阶子问题，然后其结果----n-1阶名人与最后一个人的关系进行比较。最后，不管采用两种归纳法中的哪一个，最后一步优化都是一样的，
> 即将递归方案转化为迭代方案。
> 这是一个涉及n的问题，直接联想到递归算法，于是试图去凑一个递归的程序，结果同上面的第2种方案一样。
> 由于是在n个人中"争"出一个名人，因此联想到竞赛，试着往传统竞赛算法上凑，即一个个的比并淘汰的方案，并因此发现内中的淘汰规则。
> etc. （有人补充吗？）
>
> 问题2描述：和最小连续子序列问题
>
>
> 有N个数，其中有正有负，求出其中和最小的连续子序列。（连续子序列就是a[i]~a[j]所有连续元素形成的序列，其中i，j任取）
>
> 思维方法一：
> 倒推。假设最小和子序列已经找到，我们试着去尽量挖掘这个最小和子序列的性质，每个性质都有助于另我们更"智能地"在解空间中进行搜索。我们不难发现，这
> 个假想的最小和子序列的两端元素必然是负的，否则我们可以削掉它们求得一个更小和的子序列。再进一步我们会发现，事实上这个最小和子序列从任意一段算起的
> 一个前缀/后缀的和必然也是负的，否则我们也可以将其削掉来求得一个更小和的子序列。此外，与这个最小和子序列两端紧邻着的任意一段区间的和必然是正的，
> 否则我们必然可以将其添加到我们假设的最小和序列上，以求得一个更小和的子序列。一旦挖掘出了以上三个被蕴含在结论中的条件，我们就可以更为智能地搜索解
> 空间了。
>
> 思维方法二：这是一个涉及n的问题，试着考察其子问题。我们能将问题降到n-1阶吗？n阶
> 问题里面的最小和子序列与n-1阶里面的最小和子序列有什么关联吗？如果n阶问题里面的最小和子序列不含有最后一个元素，那么它肯定同样也是n-1阶问题
> 中的最小和子序列。这种情况下我们就完全将问题降到了n-1阶。但如果它包含最后一个元素，那么一个自然的问题就是，n-1阶问题中的最小和子序列含在n
> 阶最小子序列切掉最后一个元素之后剩下的那个序列内吗？如果是的话，这种情况下问题也可以归约为n-1阶，也就是说只有n-1阶中的最小和序列才具有潜质
> 成长为n阶的最小和序列。然而，第二种情况下的答案却是否定的（试着找一个反例）。所以看上去这条路行不通。一般来说，一条路行不通之后，首先要做的就是
> 反省一下思路，看看到底什么地方出了什么问题，也许有可能修修补补之后就能够得到正确答案----想一想，我们刚才是在试着将问题降到n-1阶。那么，为什么
> ----为了能像晃筛子那样把你脑袋里那个关键的相关知识抖落出来。并且，为了方便以后能够联想，在当初吸收知识的时候就需要做最恰当的加工才行，譬如前面提
> 到的"抽象"加工，除此之外还有将知识与既有的知识框架整合，建立最多的思维连接点（或者说"钩子"）。对于知识的深浅加工所带来的影响，《找寻逝去的自我》里
> 面有精彩的介绍（里面也提到了提取线索对回忆的影响----从该意义上来说运用启发式思维方法来辅助联想，其实就是进行策略性记忆提取的过程）。最后，人类的
> 无意识思维天生有着各种各样的坏习惯，譬如前面提到的范畴陷阱就是创新思维的杀手，譬如根据表面相似性进行类比也是知识转移的一大障碍。更遑论各种各样的思维捷径了
> （我们平常进行的绝大多数思考和决策，都是通过认知捷径来进行的）。所以说，如果任由我们天生的思维方式发展，也许永远都避不开无意识中的那些陷阱，好在
> 我们除了无意识之外还多出了一层监督机制----意识。通过不断反省思维本身，时时纠正不正确的思考方式，我们就能够对其进行淬炼，最终养成良好的思维习惯。
windstorm
所以，既然a左边（从左向右符合思维习惯）所有序列不管怎么取都是正数，那么我们怎么找a呢？很简单，顺序遍历过来，序列和为正数的都可以把它们作为0，一旦找到负数，就是a的候选人，这个值就是min的候选值。然后继续往下，道理同上。
2008/5/4 windstorm <likunar...@gmail.com>:
hayate
对两道经典的算法题的思考过程作了一个总结，其中每道题目除了一种思维方法是做的时候实际用的之外，另外的是做完之后通过合情推理认为如果回到当时也是可行的思路。总结出来，为了提醒自己思路的全面性。我认为练习解题的最重要意义在于获得一般性的解题思维习惯，因为它才是跨问题的。因此在练习的过程中我总是不断反省自己的思维活动过程，这有两个作用，一是最快最有效地反省总结，从而最快地养成好习惯。二是通过考察自己的思维过程能够防止落入思路陷阱。
从获得一般性的解题思维习惯的目的来看，每道没做过的题目都有极大的价值，因为我们咀嚼的不是题目，而是解题的思维本身。
欢迎大家补充自己的！:)
问题1描述：名人问题
一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。
思维方法一：特例。考虑两个人。发现，如果A、B如果互相认识，或互相不认识，则他们都不可能是名人。如果其中之一认识另一个（不失一般性我们令A认识B），则A被淘汰。
思维方法二：倒推。假设名人已经出现，考虑名人的定义，一个名人P是指满足如下两个条件的人：
- 任取一个人Q，Q认识P。
- 任取一个人Q，P不认识Q。
接着，出于对"哪些人不符合名人的标准从而可以在我们搜索解空间的时候直接淘汰掉呢？"这个问题的询问。我们考察以上条件的反面。即"如果__则P不是名人"这个填空：
- 存在一个人Q，Q不认识P。
或
- 存在一个人Q，P认识Q。
根据这两个条件，我们实际上就可以优化穷举式的搜索，因为当比较两个人P1和P2的关系的时候，我们发现利用上面两个规则，其中最多只能有一个人具有"名人潜质"，因为根据以上规则，不管这两人之间出现认识还是不认识关系，总有一个人要被刷掉。
思维方法三：联想。联想的可能性有
- 这是一个涉及n的问题，尝试用归纳法，即考虑其子问题。如何定义子问题？两个明显的办法：1，二分为两个n/2规模的子问题。一个名人必然是这两个子问题里面的名人，所以问题归约为求解两个子问题，并在最后一个环节合并这两个子问题的解。2，考虑n-1阶的子问题。一个名人必然是n-1阶子问题中的名人，问题被归约为求解n-1阶子问题，然后其结果----n-1阶名人与最后一个人的关系进行比较。最后，不管采用两种归纳法中的哪一个，最后一步优化都是一样的，即将递归方案转化为迭代方案。
- 这是一个涉及n的问题，直接联想到递归算法，于是试图去凑一个递归的程序，结果同上面的第2种方案一样。
- 由于是在n个人中"争"出一个名人，因此联想到竞赛，试着往传统竞赛算法上凑，即一个个的比并淘汰的方案，并因此发现内中的淘汰规则。
- etc. （有人补充吗？）
问题2描述：和最小连续子序列问题
有N个数，其中有正有负，求出其中和最小的连续子序列。（连续子序列就是a[i]~a[j]所有连续元素形成的序列，其中i，j任取）
思维方法一：倒推。假设最小和子序列已经找到，我们试着去尽量挖掘这个最小和子序列的性质，每个性质都有助于另我们更"智能地"在解空间中进行搜索。我们不难发现，这个假想的最小和子序列的两端元素必然是负的，否则我们可以削掉它们求得一个更小和的子序列。再进一步我们会发现，事实上这个最小和子序列从任意一段算起的一个前缀/后缀的和必然也是负的，否则我们也可以将其削掉来求得一个更小和的子序列。此外，与这个最小和子序列两端紧邻着的任意一段区间的和必然是正的，否则我们必然可以将其添加到我们假设的最小和序列上，以求得一个更小和的子序列。一旦挖掘出了以上三个被蕴含在结论中的条件，我们就可以更为智能地搜索解空间了。
思维方法二：这是一个涉及n的问题，试着考察其子问题。我们能将问题降到n-1阶吗？n阶问题里面的最小和子序列与n-1阶里面的最小和子序列有什么关联吗？如果n阶问题里面的最小和子序列不含有最后一个元素，那么它肯定同样也是n-1阶问题中的最小和子序列。这种情况下我们就完全将问题降到了n-1阶。但如果它包含最后一个元素，那么一个自然的问题就是，n-1阶问题中的最小和子序列含在n 阶最小子序列切掉最后一个元素之后剩下的那个序列内吗？如果是的话，这种情况下问题也可以归约为n-1阶，也就是说只有n-1阶中的最小和序列才具有潜质成长为n阶的最小和序列。然而，第二种情况下的答案却是否定的（试着找一个反例）。所以看上去这条路行不通。一般来说，一条路行不通之后，首先要做的就是反省一下思路，看看到底什么地方出了什么问题，也许有可能修修补补之后就能够得到正确答案----想一想，我们刚才是在试着将问题降到n-1阶。那么，为什么一定要是n-1阶呢？譬如二分法就是试图将问题降到两个n/2阶子问题。为什么这里将问题降到n-1阶是不奏效的？因为这样的降阶无法保证我们solve 了n-1阶的子问题之后能够根据它的解来构造n阶问题的解。再仔细看看我们的方法，我们也许会发现，问题实质上出在最小和子序列可能会从n-1阶跨越到n 阶，换句话来说，问题的可能解会跨越两个子问题，这样的子问题分解得到的是不完全的子问题，我们除了需要solve两个子问题之外，还需要考虑跨越这两个子问题的潜在解，这可是个麻烦事儿。最好的子问题分解是只需要直接solve掉子问题就结了，举个例子，我们熟悉的快速排序，快速排序将一个区间根据一个中轴元素分解为两个区间之后，就将问题分解为了两个子问题，然后就只需要solve这两个子问题（将这两个区间排序），就直接了结了。它的两个子问题是完全分离的，我们不必担心任何左区间内的元素和右区间内的元素会出现乱序的情况。那么，我们的这个问题，关键就在于应该也将它分解为两个完全子问题，我们设想有某种手法，能够将我们n个数分解为两段，其中要想求全局的最小和子序列，我们只需要对这两段分别求其中的最小和子序列，然后看看哪个小即可。我们无需考察跨越这两个区间的子序列。这样一来我们就可以非常省心的将问题一步步分解为完全的子问题了。然而，到底怎样才能分解出这样的两个区段来呢？看看我们的未知数是什么。我们的未知数是要寻找这样的切分。但我们现在很茫然，n-1后面切一刀不行，二分法也不行，到底怎么切呢？看来这样盲目尝试是不行的。试试倒推吧。我们假设这样的切割已经出现了，它满足"最小和序列肯定不会跨越其切割边界"这个条件，即任取一个跨越其切割边界的子序列，都必然不是最小和序列。那么要怎样才能让一个序列不是最小和序列呢？想想上面思维方法一里面推导出的结果，最小和序列的任意前缀后缀序列必然和为负；且两端向外扩展的序列和必然为正。所以，要想让一个序列和不是最小，我们只要让情况不满足这两个条件即可。基于这个条件，细心耐心一点很快就会推导出这个切割所需满足的性质了。
思维方法三：直接联想到动态规划。然后往动态规划上硬套。硬套的过程中必然会受挫（看了下面的做法你就知道为什么不是简单的动态规划了），也许经过一定的试错，会联想到Introduction to Algorithms里面那个关于排课的问题，从而想到将区间按照结尾元素的不同来分类：（这个思路是网上抄来的，关键是"考虑以某个a[x]终止的所有子序列"这一步很是摸不着头绪。有谁能够提供这个做法背后的思维过程吗？）
设 f[x] 为以 a[x] 终止且包含 a[x] 的最小序列的和，有：
f[1] = a[1];
f[x+1] = f[x] < 0 ? f[x] + a[x+1] : a[x+1]
那么最小子序列的和就是 f[1] .. f[n] 中最小的一个。参考：
P.S. 更新了一下"跟波利亚学解题"到rev#1版，主要添加以下一段：
5. 练习，练习
本质上，练习并不产生新能力。然而练习最重要的一个作用就是将外显记忆转化为内隐记忆。用大白话来说就是将平时需要用脑子去想（参与）的东西转化为内在的习惯。譬如我们一开始学骑自行车的时候需要不断提醒自己注意平衡，但随着不断的联系，这种技能就内化成了所谓的程序式记忆（内隐记忆的一种），从而就算你一边骑车一边进行解题这样需要消耗大量脑力的活动，也无需担心失去平衡（不过撞树是完全可能的，但那是另一回事）。
同样，对于解题中的思维方法来说，不断练习这些思维方法就能做到无意识间就能运用自如，大大降低了意识的负担和加快了解题速度。
不过，并非所有的练习方法都是等效的，有些练习方法肯定要比另一些更有效率。譬如就解题来说，解题是一项涉及到人类最高级思维机制的活动，其中尤其是推理（归纳和演绎）和联想。而后者中又尤数联想是最麻烦的，前面提到，绝大多数时候启发式方法实质上都是在为联想服务 ----为了能像晃筛子那样把你脑袋里那个关键的相关知识抖落出来。并且，为了方便以后能够联想，在当初吸收知识的时候就需要做最恰当的加工才行，譬如前面提到的"抽象"加工，除此之外还有将知识与既有的知识框架整合，建立最多的思维连接点（或者说"钩子"）。对于知识的深浅加工所带来的影响，《找寻逝去的自我》里面有精彩的介绍（里面也提到了提取线索对回忆的影响----从该意义上来说运用启发式思维方法来辅助联想，其实就是进行策略性记忆提取的过程）。最后，人类的无意识思维天生有着各种各样的坏习惯，譬如前面提到的范畴陷阱就是创新思维的杀手，譬如根据表面相似性进行类比也是知识转移的一大障碍。更遑论各种各样的思维捷径了（我们平常进行的绝大多数思考和决策，都是通过认知捷径来进行的）。所以说，如果任由我们天生的思维方式发展，也许永远都避不开无意识中的那些陷阱，好在我们除了无意识之外还多出了一层监督机制----意识。通过不断反省思维本身，时时纠正不正确的思考方式，我们就能够对其进行淬炼，最终养成良好的思维习惯。反之被动的练习虽然也能熟能生巧，但势必花的时间更多，而且对于涉及复杂的思维机制的解题活动来说，远远不是通过钱眼往油壶里面倒油这样简单的活动所能类比的，倒油不像思维活动那样有形形色色的陷阱，倒油不需要联想和推理，倒油甚至几乎完全不需要意识的辅助性参与，除了集中注意力（而解题活动就算对于极其熟练的人来说也不断需要大量的意识参与）。所以对于前者，良好的思维习惯至关重要，而反省加上运用正确的思维方法则是最终养成良好思维习惯的途径。
练习还有另外一个很重要的作用，就是增加领域知识（关于知识在问题解决中的作用，前面已经提到过）。我们看到很多人，拿到一道题目立即脑子里就反应出解法，这个反应快到他自己都不能意识到背后有什么逻辑。这是因为既有的知识（我们常说的"无他，实在是题做得太多了"）起到了极大的作用，通过对题目中几个关键元素或结构的感知，大脑中的相关知识迅速被自动提取出来。而对于知道但不熟悉相应知识（譬如很早我们就知道归纳法，但是很久以后我们才真正能够做到面对任何一道可能用归纳法的题目就立即能够想到运用归纳法），或者干脆就不知道该知识的人来说，就需要通过启发法来辅助联想或探索了。后者可以一定程度上代偿对知识的不够熟悉，但在一些时候知识的缺失则是致命的（参见上面第2点）。不过要注意的是，那种看到题目直接反应出答案的或许也不是纯粹的好事，因为这样的解题过程严重依赖于既有知识，尤其是做过的类似的题目，其思维过程绝大部分运用的是联想或类比，而非演绎或归纳。更重要的是，联想也分两种，被动联想和策略性联想（参考《找寻逝去的自我》），这里用的却是被动联想。所以，能直接反应出答案并不代表遇到真正新颖的题目的时候的解决能力，后者由于不依赖于既有领域知识，就真正需要看一个人的思维能力和习惯究竟如何了。
kicool
pongba
名人问题，无论是思维方式1还是思维方式2，这样淘汰下来，比如a，b，c，d都淘汰了，发现e在剩下的人里面符合名人的标准，但也不能说明e就是名人啊，因为e和abcd的关系已经被删除无法判断了。
当然还可以回溯来解，但这样算法貌似就不是O(n)了吧？
还是O(n)的，因为只需回溯比较e与abcd的关系，即+O(n)，O(n)+O(n)=O(n)
kicool
鋆邓
2、关于动态规划，我提醒部分习惯于看到动态规划就以直接写出函数为目标的同学们：
部分动态规划题目不适合直接将最终答案当作函数值来设计递推函数，往往用一些中间的结果。比如我们要找整个解空间的最优解，但整个解空间的最优解不存在直接的递推关系，那么可否考虑设计比如"以该位置结尾"的解空间，其最优解很大可能存在递推关系。
随后将解空间综合比较，可得到整体的最优解。（当然，在算法中，可以一边求一边解）
用这种方法，在思考算法的时候，一定要确保你的递推过程遍历到了整个解空间。
顺便，pongba，我有一些不错的介于数学和算法之间的题目，如何推荐给您？
鋆邓
没仔细想，但应该没错
转化成经典已有问题也是许多动态规划问题的解题思路
windstorm
2008/5/4 pongba <pon...@gmail.com>:
pongba
1、这一题我觉得过于明显了，对于"他不认识其他所有人"这一要求。一次扫描找出唯一的潜在者，再一次扫描确认就可。
2、关于动态规划，我提醒部分习惯于看到动态规划就以直接写出函数为目标的同学们：
部分动态规划题目不适合直接将最终答案当作函数值来设计递推函数，往往用一些中间的结果。比如我们要找整个解空间的最优解，但整个解空间的最优解不存在直接的递推关系，那么可否考虑设计比如"以该位置结尾"的解空间，其最优解很大可能存在递推关系。
随后将解空间综合比较，可得到整体的最优解。（当然，在算法中，可以一边求一边解）
用这种方法，在思考算法的时候，一定要确保你的递推过程遍历到了整个解空间。
顺便，pongba，我有一些不错的介于数学和算法之间的题目，如何推荐给您？
那太好了，多谢:-)
pongba
1、这一题我觉得过于明显了，对于"他不认识其他所有人"这一要求。一次扫描找出唯一的潜在者，再一次扫描确认就可。
2、关于动态规划，我提醒部分习惯于看到动态规划就以直接写出函数为目标的同学们：
部分动态规划题目不适合直接将最终答案当作函数值来设计递推函数，往往用一些中间的结果。比如我们要找整个解空间的最优解，但整个解空间的最优解不存在直接的递推关系，那么可否考虑设计比如"以该位置结尾"的解空间，其最优解很大可能存在递推关系。
随后将解空间综合比较，可得到整体的最优解。（当然，在算法中，可以一边求一边解）
用这种方法，在思考算法的时候，一定要确保你的递推过程遍历到了整个解空间。
恩，鋆邓兄第二点说得很对。non-trivial的动态规划往往是不能整体降阶的。
我想补充的是，如何寻找那个存在着递推关系的部分解空间，是不是有一些较为一般化的启发式思路呢？譬如第二个例子里面的考虑以a[x]结尾的所有子序列，一个解题者可能遵循什么样的思维过程便能够想到"考虑以a[x]结尾的所有子序列"呢？也许在知道了答案之后来看这个做法很显然，然而我觉得事前倒不是那么显然的。
从一个最一般的层面来说，其实这就是一个关于如何分割解空间的问题，一旦将注意力放到"如何分割解空间"这个问题上，也许离发现可以根据子序列的头元素的不同或尾元素的不同来分类就不是遥远的事情了。
不过对于这道特定的题目，我还是怀疑想出答案的人是通过上面这个过程想到的。如果鋆邓兄当时想到了那个DP解法，那么当时的思维过程是怎样的呢？
kicool
对两道经典的算法题的思考过程作了一个总结，其中每道题目除了一种思维方法是做的时候实际用的之外，另外的是做完之后通过合情推理认为如果回到当时也是可行的思路。总结出来，为了提醒自己思路的全面性。我认为练习解题的最重要意义在于获得一般性的解题思维习惯，因为它才是跨问题的。因此在练习的过程中我总是不断反省自己的思维活动过程，这有两个作用，一是最快最有效地反省总结，从而最快地养成好习惯。二是通过考察自己的思维过程能够防止落入思路陷阱。
从获得一般性的解题思维习惯的目的来看，每道没做过的题目都有极大的价值，因为我们咀嚼的不是题目，而是解题的思维本身。
欢迎大家补充自己的！:)
问题1描述：名人问题
一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。
思维方法一：特例。考虑两个人。发现，如果A、B如果互相认识，或互相不认识，则他们都不可能是名人。如果其中之一认识另一个（不失一般性我们令A认识B），则A被淘汰。
思维方法二：倒推。假设名人已经出现，考虑名人的定义，一个名人P是指满足如下两个条件的人：
- 任取一个人Q，Q认识P。
- 任取一个人Q，P不认识Q。
接着，出于对"哪些人不符合名人的标准从而可以在我们搜索解空间的时候直接淘汰掉呢？"这个问题的询问。我们考察以上条件的反面。即"如果__则P不是名人"这个填空：
- 存在一个人Q，Q不认识P。
或
- 存在一个人Q，P认识Q。
根据这两个条件，我们实际上就可以优化穷举式的搜索，因为当比较两个人P1和P2的关系的时候，我们发现利用上面两个规则，其中最多只能有一个人具有"名人潜质"，因为根据以上规则，不管这两人之间出现认识还是不认识关系，总有一个人要被刷掉。
思维方法三：联想。联想的可能性有
- 这 是一个涉及n的问题，尝试用归纳法，即考虑其子问题。如何定义子问题？两个明显的办法：1，二分为两个n/2规模的子问题。一个名人必然是这两个子问题里 面的名人，所以问题归约为求解两个子问题，并在最后一个环节合并这两个子问题的解。2，考虑n-1阶的子问题。一个名人必然是n-1阶子问题中的名人，问 题被归约为求解n-1阶子问题，然后其结果----n-1阶名人与最后一个人的关系进行比较。最后，不管采用两种归纳法中的哪一个，最后一步优化都是一样的， 即将递归方案转化为迭代方案。
- 这是一个涉及n的问题，直接联想到递归算法，于是试图去凑一个递归的程序，结果同上面的第2种方案一样。
- 由于是在n个人中"争"出一个名人，因此联想到竞赛，试着往传统竞赛算法上凑，即一个个的比并淘汰的方案，并因此发现内中的淘汰规则。
- etc. （有人补充吗？）
问题2描述：和最小连续子序列问题
有N个数，其中有正有负，求出其中和最小的连续子序列。（连续子序列就是a[i]~a[j]所有连续元素形成的序列，其中i，j任取）
思维方法一： 倒推。假设最小和子序列已经找到，我们试着去尽量挖掘这个最小和子序列的性质，每个性质都有助于另我们更"智能地"在解空间中进行搜索。我们不难发现，这 个假想的最小和子序列的两端元素必然是负的，否则我们可以削掉它们求得一个更小和的子序列。再进一步我们会发现，事实上这个最小和子序列从任意一段算起的 一个前缀/后缀的和必然也是负的，否则我们也可以将其削掉来求得一个更小和的子序列。此外，与这个最小和子序列两端紧邻着的任意一段区间的和必然是正的， 否则我们必然可以将其添加到我们假设的最小和序列上，以求得一个更小和的子序列。一旦挖掘出了以上三个被蕴含在结论中的条件，我们就可以更为智能地搜索解 空间了。
思维方法二：这是一个涉及n的问题，试着考察其子问题。我们能将问题降到n-1阶吗？n阶 问题里面的最小和子序列与n-1阶里面的最小和子序列有什么关联吗？如果n阶问题里面的最小和子序列不含有最后一个元素，那么它肯定同样也是n-1阶问题 中的最小和子序列。这种情况下我们就完全将问题降到了n-1阶。但如果它包含最后一个元素，那么一个自然的问题就是，n-1阶问题中的最小和子序列含在n 阶最小子序列切掉最后一个元素之后剩下的那个序列内吗？如果是的话，这种情况下问题也可以归约为n-1阶，也就是说只有n-1阶中的最小和序列才具有潜质 成长为n阶的最小和序列。然而，第二种情况下的答案却是否定的（试着找一个反例）。所以看上去这条路行不通。一般来说，一条路行不通之后，首先要做的就是 反省一下思路，看看到底什么地方出了什么问题，也许有可能修修补补之后就能够得到正确答案----想一想，我们刚才是在试着将问题降到n-1阶。那么，为什么 一定要是n-1阶呢？譬如二分法就是试图将问题降到两个n/2阶子问题。为什么这里将问题降到n-1阶是不奏效的？因为这样的降阶无法保证我们solve 了n-1阶的子问题之后能够根据它的解来构造n阶问题的解。再仔细看看我们的方法，我们也许会发现，问题实质上出在最小和子序列可能会从n-1阶跨越到n 阶，换句话来说，问题的可能解会跨越两个子问题，这样的子问题分解得到的是不完全的子问题，我们除了需要solve两个子问题之外，还需要考虑跨越这两个 子问题的潜在解，这可是个麻烦事儿。最好的子问题分解是只需要直接solve掉子问题就结了，举个例子，我们熟悉的快速排序，快速排序将一个区间根据一个 中轴元素分解为两个区间之后，就将问题分解为了两个子问题，然后就只需要solve这两个子问题（将这两个区间排序），就直接了结了。它的两个子问题是完 全分离的，我们不必担心任何左区间内的元素和右区间内的元素会出现乱序的情况。那么，我们的这个问题，关键就在于应该也将它分解为两个完全子问题，我们设 想有某种手法，能够将我们n个数分解为两段，其中要想求全局的最小和子序列，我们只需要对这两段分别求其中的最小和子序列，然后看看哪个小即可。我们无需 考察跨越这两个区间的子序列。这样一来我们就可以非常省心的将问题一步步分解为完全的子问题了。然而，到底怎样才能分解出这样的两个区段来呢？看看我们的 未知数是什么。我们的未知数是要寻找这样的切分。但我们现在很茫然，n-1后面切一刀不行，二分法也不行，到底怎么切呢？看来这样盲目尝试是不行的。试试 倒推吧。我们假设这样的切割已经出现了，它满足"最小和序列肯定不会跨越其切割边界"这个条件，即任取一个跨越其切割边界的子序列，都必然不是最小和序 列。那么要怎样才能让一个序列不是最小和序列呢？想想上面思维方法一里面推导出的结果，最小和序列的任意前缀后缀序列必然和为负；且两端向外扩展的序列和 必然为正。所以，要想让一个序列和不是最小，我们只要让情况不满足这两个条件即可。基于这个条件，细心耐心一点很快就会推导出这个切割所需满足的性质了。
思维方法三：直接联想到动态规划。然后往动态规划上硬套。硬套的过程中必然会受挫（看了下面的做法你就 知道为什么不是简单的动态规划了），也许经过一定的试错，会联想到Introduction to Algorithms里面那个关于排课的问题，从而想到将区间按照结尾元素的不同来分类：（这个思路是网上抄来的，关键是"考虑以某个a[x]终止的所有 子序列"这一步很是摸不着头绪。有谁能够提供这个做法背后的思维过程吗？）
设 f[x] 为以 a[x] 终止且包含 a[x] 的最小序列的和，有：
f[1] = a[1];
f[x+1] = f[x] < 0 ? f[x] + a[x+1] : a[x+1]
那么最小子序列的和就是 f[1] .. f[n] 中最小的一个。参考：
P.S. 更新了一下"跟波利亚学解题"到rev#1版，主要添加以下一段：5. 练习，练习
本质上，练习并不产生新能力。然而练习最重要的一个作用就是将外显记忆转化为内隐记忆。用大白话来说就是将平时需要用脑子去想（参与）的东西转化为内在的习惯。譬如我们一开始学骑自行车的时候需要不断提醒自己注意平衡，但随着不断的联系，这种技能就内化成了所谓的程序式记忆（内隐记忆的一种），从而就算你一边骑车一边进行解题这样需要消耗大量脑力的活动，也无需担心失去平衡（不过撞树是完全可能的，但那是另一回事）。
同样，对于解题中的思维方法来说，不断练习这些思维方法就能做到无意识间就能运用自如，大大降低了意识的负担和加快了解题速度。
不过，并非所有的练习方法都是等效的，有些练习方法肯定要比另一些更有效率。譬如就解题来说，解题是一项涉及到人类 最高级思维机制的活动，其中尤其是推理（归纳和演绎）和联想。而后者中又尤数联想是最麻烦的，前面提到，绝大多数时候启发式方法实质上都是在为联想服务 ----为了能像晃筛子那样把你脑袋里那个关键的相关知识抖落出来。并且，为了方便以后能够联想，在当初吸收知识的时候就需要做最恰当的加工才行，譬如前面提 到的"抽象"加工，除此之外还有将知识与既有的知识框架整合，建立最多的思维连接点（或者说"钩子"）。对于知识的深浅加工所带来的影响，《找寻逝去的自我》里 面有精彩的介绍（里面也提到了提取线索对回忆的影响----从该意义上来说运用启发式思维方法来辅助联想，其实就是进行策略性记忆提取的过程）。最后，人类的 无意识思维天生有着各种各样的坏习惯，譬如前面提到的范畴陷阱就是创新思维的杀手，譬如根据表面相似性进行类比也是知识转移的一大障碍。更遑论各种各样的思维捷径了 （我们平常进行的绝大多数思考和决策，都是通过认知捷径来进行的）。所以说，如果任由我们天生的思维方式发展，也许永远都避不开无意识中的那些陷阱，好在 我们除了无意识之外还多出了一层监督机制----意识。通过不断反省思维本身，时时纠正不正确的思考方式，我们就能够对其进行淬炼，最终养成良好的思维习惯。 反之被动的练习虽然也能熟能生巧，但势必花的时间更多，而且对于涉及复杂的思维机制的解题活动来说，远远不是通过钱眼往油壶里面倒油这样简单的活动所能类 比的，倒油不像思维活动那样有形形色色的陷阱，倒油不需要联想和推理，倒油甚至几乎完全不需要意识的辅助性参与，除了集中注意力（而解题活动就算对于极其 熟练的人来说也不断需要大量的意识参与）。所以对于前者，良好的思维习惯至关重要，而反省加上运用正确的思维方法则是最终养成良好思维习惯的途径。
鋆邓
baibaichen
关于名人问题，可以这样理解，
1) 每一个人是一个顶点
2）如果A认识B，则成在一条从A到B的有向边
根据定义，名人不认识任何其他人，所以，我们是在图中找一个没有后续的顶点。 显然这里是O(N)。
pongba
Justin L
On May 3, 11:15 pm, pongba <pon...@gmail.com> wrote:
>
> *问题1描述：名人问题*
> 一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。
>
>
> - 任取一个人Q，Q认识P。
> - 任取一个人Q，P不认识Q。
> 接着，出于对"哪些人不符合名人的标准从而可以在我们搜索解空间的时候直接淘汰掉呢？"这个问题的询问。我们考察以上条件的反面。即"如果__则P不是名人"这个填空：
>
>
> 或
>
> - 存在一个人Q，P认识Q。
> 根据这两个条件，我们实际上就可以优化穷举式的搜索，因为当比较两个人P1和P2的关系的时候，我们发现利用上面两个规则，其中最多只能有一个人具有"名人潜质"，因为根据以上规则，不管这两人之间出现认识还是不认识关系，总有一个人要被刷掉。
>
1) 按照我理解，题目条件是这样的：
名人不认识任何其他人。（名人不认识名人，也不认识普通非名人）
所有其他人都认识名人。（其他人就是指非名人的人。）
按照这种理解，这里是推不出来名人只能有一名的。有两个名人，一个名人不认识另外一个名人。这符合题目描述。
2) pongda的理解，我看可能是：
所有其他人（意思指这个人以外的所有的人）都认识名人。
要是按照名人不会只有一名来看，题目会稍微复杂一些。
