Divide and Conquer

分治

• 大师定理->用来评估分冶的效率
• 选择第k小的数字的问题
  思路：利用分冶的思路将数组中的元素划分为大于v的、等于v、以及小于v的三种情况，并根据k与mid的大小关系来决定递归的方向，具体实现借助快速排序的代码。实现链接：http://www.cnblogs.com/imAkaka/archive/2012/03/28/2421156.html http://blog.csdn.net/fanzitao/article/details/7617223
• 分冶与动态规划的不同：分冶是划分为问题规模小很多的子问题，而动态规划减少时间的原因在于避免了无用的搜索。

要理解分治和backtracking的区别:

Backtracking is a general algorithm for finding all (or some)
solutions to some computational problems, notably constraint
satisfaction problems, that incrementally builds candidates to the
solutions, and abandons a candidate ("backtracks") as soon as it
determines that the candidate cannot possibly be completed to a valid
solution.
分治是一定有处理子问题的调用，将大的问题分而治之。

1 URAL 11129
题目大意：给定0~n-1的自然数,给出其子序列不可能出现等差序列的一种排列，1243是不符合条件的，因为其子序列123为子序列。
思路：通过递归，首先将序列分开奇偶序列，这样奇数序列和偶数序列之间是不会产生等差序列的了，从而将大的问题转化为较小的问题，然后递归下去，注意下边界条件即可。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int array[10010], tmp[10010];
void Dvide(int l, int r)
{
    if(r - l <= 1) return;
    for(int i = l; i <= r; i++)
        tmp[i] = array[i];
    int i, j;
    for(i = l, j = l; j <= r; j += 2, i++){
        array[i] = tmp[j];
    }
    for(j = l + 1; j <= r; j += 2, i++){
        array[i] = tmp[j];
    }
    Dvide(l, (l + r) / 2);
    Dvide((l + r) / 2 + 1, r);
}
int main()
{
    int n;
    while(scanf("%d", &n) && n){
        for(int i = 0; i < n; i++)
            array[i] = i;
        Dvide(0, n - 1);
        printf("%d:", n);
        for(int i = 0; i < n; i++)
            printf(" %d", array[i]);
        printf("\n");
    }
    return 0;
}

关于子序列的问题还有很多，如最大子序列、最长公共子串、最长公共子序列、最长递增子序列等。这些问题都放到dp专题里边了。

1. poj1664分苹果问题
   题目链接:http://poj.org/problem?id=1664
   题目描述:把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
   思路:
   这个问题感觉类似组合数的问题。
   【1】苹果比盘子少，那么该问题就和m个苹果m个盘子的问题一样，问题规模被减小，解法不变。
   【2】苹果比盘子多，这时侯的解由两部分构成：所有盘子都有苹果+不是所有盘子都有苹果。其中不是所有盘子都有苹果这种情况和至少有一个盘子空着这种情况是一样的，这样问题就变成了m个苹果放在n-1个盘子里！问题规模减小，解法同样不变。而所有盘子都有苹果说明每个盘子至少有一个苹果，说明有n个苹果是固定的，变数是剩下的m-n个苹果！那么这个问题和m-n个苹果放在n个盘子里是一致的！问题规模减小，解法不变。如果问题规模减小到只剩一个盘子或者没有苹果了，那么解法就一种，我们要返回1。综上我们可以用递归来解决这个问题。
   关键代码:

int count(int m,int n)//m apples  
{  
   if(m==0||n==1) return 1;  
   if(n>m) return count(m,m);  
   return count(m-n,n)+count(m,n-1);  
}

1. leetcode Different Ways to Add Parentheses

   class Solution {
   public:
   vector divide(string input) {

       vector<int> ans;
       //用来标记是否是一个表达式
       bool isAlgo = false;
       for(int i = 0; i < input.size(); ++i) {
           if (input[i] == '*') {
               vector<int> ans1 = divide(input.substr(0, i));
               vector<int> ans2 = divide(input.substr(i+1, input.size() - i - 1));
               for(int i = 0; i < ans1.size(); ++i) {
                   for(int j = 0; j < ans2.size(); ++j) {
                       ans.push_back(ans1[i]*ans2[j]);
                   }
               }
               isAlgo = true;
           } else if (input[i] == '-') {
               vector<int> ans1 = divide(input.substr(0, i));
               vector<int> ans2 = divide(input.substr(i+1, input.size() - i - 1));
               for(int i = 0; i < ans1.size(); ++i) {
                   for(int j = 0; j < ans2.size(); ++j) {
                       ans.push_back(ans1[i]-ans2[j]);
                   }
               }
               isAlgo = true;
           } else if (input[i] == '+') {
               vector<int> ans1 = divide(input.substr(0, i));
               vector<int> ans2 = divide(input.substr(i+1, input.size() - i - 1));
               for(int i = 0; i < ans1.size(); ++i) {
                   for(int j = 0; j < ans2.size(); ++j) {
                       ans.push_back(ans1[i]+ans2[j]);
                   }
               }
               isAlgo = true;
           }
       }
       if (isAlgo)
           return ans;
       else
           return vector<int>{stoi(input)};
   }
   
   vector<int> diffWaysToCompute(string input) {
       if (input.size() == 0)
           return vector<int>{};
       return divide(input);
   }
   

   };