<commit_before>---
title: 分治法与动态规划
date: 2016-02-01 16:28
---

这里主要借助max subarray，以及几个其他的例子，分析一下分治法和动态规划的基本思想。

## divide and conqure
分治法的思想非常简单：1. divide成与原问题一模一样的子问题; 2. conquer; 3. combine。

要真正理解divide and conqure是什么，首先得想一想divide and conquer不是什么。

譬如：在一个长度为n的数组里找至少出现了n/2次的majority element。

#### 假设已知majority element一定存在：

1. 一个最直观且最不分治的做法：给数组排个序，majority element一定是中位数。这种做法的实质是用sequential order来encode整个无序的数组，问题始终被作为一个整体来看待（否则就无法对其进行编码）。然而这显然是个overkill。中位数左右子串精确的有序化对我来说是毫无用处的。

2. 于是我们很自然地想到一个不那么浪费的做法：quick selection。每当一个随机元素被partition到正确的位置，如果它在中位数的左边，问题就变成了在其右边的子串继续select—— 一个与原问题一模一样的smaller instance。在这里，我们放弃了整个数组的精确order，从而把原问题prune成了一个又一个更小的子问题。assume that on average, 每一次prune后的子串长度是上一次的1/c，recursion应为T(n) = cT(n/c) + theta(1)。由于c的随机性，在找到中位数之前，我们仍然需要一次又一次地conquer那些已经访问过的子串，只是这些子串变小了。每一次conquer之所以能够让问题的规模变小，是因为partition说白了仍然是在用一种比起sort更为slack的order建立起数组中的秩序，而这种秩序是我们完全不需要的东西。

3. 真正relevant的事情是：majority element之所以是majority仅仅是因为出现的次数多，我们根本不在意它比谁大或比谁小。如果每个majority element能吃掉一个其他元素，那么全吃完后剩下的就只有我们的majority element了。怎么model这个解法呢？透过分治法的透镜，我们看到，如果一个元素在n个元素里出现的次数超过一半，那么把n个元素平均分成左右两半，这个元素要么在左边出现超过一半，要么在右边出现超过一半，要么在两边都超过一半。把数组不断地切得更小，这个性质不会改变。由此可推断出两种可能：

    1) 当子串长度减少到2时，“超过一半”==“两个都是”。也就是说，如果数组里只有一组连续两个相等的元素，那一定是我们要找的majority element；如果数组里有多组两个连续相等的元素，那么majority element一定比其他所有组至少多一组。

    2) 当子串长度不足2，即=1时，如果其counterpart子串不包含majority element，那么这一个元素必然是majority element。

因此，我们可以充分利用“majority element一定存在”这个knowledge，只遍历一次整个数组，用当前找到的majority消耗掉非majority，最后剩下的就是真正的majority了。

### 假设不知道majority element是否存在：

在解法3中，一旦我们用非majority消耗掉当前维护的majority，就再也不可能知道曾经发生过什么。因此解法3不适用。

-

由此可以看出，分治法是一种思想，而不是一种算法。在解法2中，我们进行了显式的divide, conquer and combine（丢弃半个子串可以理解为一种conquer），然而这个分治法用得并不聪明；在解法3中，最终实际的算法其实是iteratively过一遍数组，似乎并没有像通常的分治法那样recursively divide或combine任何东西，然而其之所以流b，究其根本是用分治法对问题的结构进行了正确的剖析。

-

恩所以。。对于max subarray问题如果也试试分治法的话：如果将整个数组分成左右两半，max subarray要么出现在左边，要么出现在右边，要么横跨左右两边（听起来还蛮废话的）。

显然，“横跨左右两边”对于当前数组来说并不是一个一模一样的smaller instance。它多了一个“必须横跨中点”的这个原问题中并没有的限制，因此问题的性质被改变了。所以我们需要另外计算一下“横跨中点的最长子串”。需要注意的是，虽然横跨中点的最长子串会与左子串或/和右子串共享数组中的资源，它们解决问题的过程和计算的结果是彼此独立的。而也正是这些彼此独立的重复访问，使得分治法在解决这个问题时显得颇为不智：其recursion为T(n) = 2T(n/2) + theta(n)，complexity = O(nlgn)。

## dynamic programming

对于上例中分治法需要重复解决的子问题，动态规划只解决一次。它做到这个的方式就是：记住。at the cost of extra memory.

譬如说，计算第n个斐波那契数时，因为第n个数的解包含着所有小于n的数的解的贡献，所以每算出一个小于n的数，记在一个table里；

譬如说，计算如何cut一个长度为n的rod最赚钱时，因为每个局部最优cut堆起来组成了全局最优cut，所以在到达n之前每决定一个cut，记在一个table里；

同样，在计算max subarray时，每个元素都试图对最大子串做出自己的一份贡献。有时候可能会不进反退，然而只要当前累计总量还大于0，之前的一切努力就是有意义的；一旦当前总数小于0了，就意味着还不如全部丢掉从头开始。因此每向前走一步，我们就把当前这个元素的贡献加进来看一看，只要大于0，就记在一个table里。事实上，既然我们只需要一个最大的子串（而不是所有不为0的子串），那么这个table也是不必要的。我们需要的只是一个当前找到的最大值，如果某个时刻更大的出现了，就把它更新一下。

## 结论

max subarray的动态规划算法其实和majority element的解法3的“消耗”思想很相似—— 首先无论如何总得维护一个当前全局最优解这个没啥好说的，然后在一步步前进的过程中，只要这个最优解还没有被消耗完，我们就暂时记着它，看看还会不会有更好的事情发生。

所以也许会有人把majority element的解法3称为动态规划？可是我依然认为真正重要的是用分治法的思想把问题divide到只剩1个或2个元素的时候，我们可以推断出什么。

按照算法导论的说法，可以用subproblem graph model的问题才是真正的动态规划问题。这样说起来的话，max subarray的所谓动态规划算法并没有什么subproblem graph结构可言呢。。啊反正到头来叫喵还是咪也并不那么重要吧。

-

总之似乎可以总结出的规律是：

1. 不管是分治法还是动态规划，子问题必须彼此独立。

所谓的彼此不独立，指的是这样一种情况：当子问题A使用某些资源的时候，这些资源对同级别的子问题B就不再available了。（比如要计算一个weighted directed graph中的longest simple path的话）。

2. 如果存在彼此重叠且一模一样的子问题，暗示着可以用动态规划解。

啊写不动了明天接着写！
<commit_msg>删除半年前愚蠢的胡说八道<commit_after>---
title: 分治法与动态规划
date: 2016-02-01 16:28
---

## divide and conqure
要真正理解divide and conqure是什么，首先得想一想divide and conquer不是什么。

譬如：在一个长度为n的数组里找至少出现了n/2次的majority element。

#### 假设已知majority element一定存在：

1. 一个最直观且最不分治的做法：给数组排个序，majority element一定是中位数。这种做法的实质是用sequential order来encode整个无序的数组，问题始终被作为一个整体来看待（否则就无法对其进行编码）。然而这显然是个overkill。中位数左右子串精确的有序化对我来说是毫无用处的。

2. 于是我们很自然地想到一个不那么浪费的做法：quick selection。每当一个随机元素被partition到正确的位置，如果它在中位数的左边，问题就变成了在其右边的子串继续select—— 一个与原问题一模一样的smaller instance。在这里，我们放弃了整个数组的精确order，赢得了一个log量级的时间；但在partition到中位数之前，我们仍然需要一次又一次地conquer那些其实已经访问过的子串。每一次conquer之所以能够让问题的规模变小，是因为partition说白了仍然是在用一种比起sort更为slack的order建立起数组中的秩序，而这种秩序是我们完全不需要的东西。

3. 真正relevant的事情是：majority element之所以是majority仅仅是因为出现的次数多，我们根本不在意它比谁大或比谁小。如果每个majority element能吃掉一个其他元素，那么全吃完后剩下的就只有我们的majority element了。怎么model这个解法呢？透过分治法的透镜，我们看到，如果一个元素在n个元素里出现的次数超过一半，那么把n个元素平均分成左右两半，这个元素要么在左边出现超过一半，要么在右边出现超过一半，要么在两边都超过一半。把数组不断地切得更小，这个性质不会改变。由此可推断出两种可能：

    1) 当子串长度减少到2时，“超过一半”==“两个都是”。也就是说，如果数组里只有一组连续两个相等的元素，那一定是我们要找的majority element；如果数组里有多组两个连续相等的元素，那么majority element一定比其他所有组至少多一组。

    2) 当子串长度不足2，即=1时，如果其counterpart子串不包含majority element，那么这一个元素必然是majority element。

因此，我们可以充分利用“majority element一定存在”这个knowledge，只遍历一次整个数组，用当前找到的majority消耗掉非majority，最后剩下的就是真正的majority了。

### 假设不知道majority element是否存在：

在解法3中，一旦我们用非majority消耗掉当前维护的majority，就再也不可能知道曾经发生过什么。因此解法3不适用。

-

所以分治法是一种思想而不是一种算法。关键在于如何聪明地切分问题的结构。在解法2中，我们进行了显式的divide, conquer and combine（丢弃半个子串可以理解为一种conquer），然而这个分治法用得并不聪明；在解法3中，最终实际的算法其实是iteratively过一遍数组，似乎并没有像通常的分治法那样recursively divide或combine任何东西，然而其之所以流b，究其根本是用分治法对问题的结构进行了正确的剖析。

-

恩所以。。对于max subarray问题如果也试试分治法的话：如果将整个数组分成左右两半，max subarray要么出现在左边，要么出现在右边，要么横跨左右两边（听起来还蛮废话的）。

显然，“横跨左右两边”多了一个“必须横跨中点”的这个原问题中并没有的限制，因此问题的性质被改变了。所以我们需要另外计算一下“横跨中点的最长子串”。需要注意的是，虽然横跨中点的最长子串会与左子串或/和右子串共享数组中的资源，但它们解决问题的过程和计算的结果是彼此独立的。而也正是这些彼此独立的重复访问，使得分治法在解决这个问题时显得颇为不智。



{'fraction_non_alphanumeric': 0.07825579131788982, 'fraction_numerical': 0.01304263188631497, 'mean_word_length': 16.77854671280277, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2970119', 'n_tokens_mistral': 3979, 'n_tokens_neox': 4511, 'n_words': 161}