先简单介绍几个基础概念：
递归 递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环。 其中，迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。典型的应用有深度搜索dfs
迭代 递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。 当然很多情况都是多种循环混合采用，这要根据具体需求.在循环的次数较大的时候，迭代的效率明显高于递归,但是不易于理解。典型应用有bfs中遍历队列。
对于斐波那契数列
// 递归方法 int fibonacci_sequence_recursion(int n) { return (n < 2) ? n : fibonacci_sequence_recursion(n - 1) + fibonacci_sequence_recursion(n - 2); } // 迭代方法 int fibonacci_sequence_loop(int n) { if (n < 2) return n; int before = 0; int last = 1; while (1 < n--) { last = before + last; before = last - before; } return last; }
五大基本算法：
穷举 enumerate
枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。 枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？ 枚举的范围是什么？是所有的内容都需要枚举吗？
在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销。
贪心 greedy
在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
分治 divide-and-conquer
把问题分解成规模小的问题，再去递归(或迭代)解决。
注意二分搜索(binary-search)每次都要舍弃一半，从留下的一半中寻找目标；而分治法把一个大问题分成两个或多个小问题
- 归并排序
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def move(n, a, b, c):
if n == 1:
print(a, '-->', c)
return
move(n-1, a, c, b)
print(a, '-->', c)
move(n-1, b, a, c)
a = input("请输入汉尼塔A的个数: ")
move(int(a), 'A', 'B', 'C')
"""
总次数一定为 2^n - 1
可以把盘子看成两部分，最下面的第n个和上面的n-1个，完成所有盘子的从a到c可以分解为3步:
1.把上面n-1个盘子从a移动到b
2.把最下面的第n个盘子从a移动到c
3.把在b上的n-1个盘子移动到c
这样从最后一步往前n-1个分解，只不过步骤1和3中的移动前n-1个不是借助b从a移动到c，而分别是，借助c从a到b和借助a从b到c。
这样就分解成了n-1个盘子的汉诺塔问题，一直用这三步迭代分解一直到n等于1。
"""
回溯 backtracking
回溯法简单来说就是按照深度优先的顺序，穷举所有可能性的算法，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。一旦不符合条件，那么就退回到上一个状态，省去了继续往下探索的时间。所以根据这类问题，一般会有优化剪枝策略以及启发式搜索策略。
多说无益，给出几个具体例子：
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后， 使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解[1]。*/
#include <iostream> using namespace std; const int N = 8; int arr[10], total_cnt; // arr记录每一行(X)皇后的Y坐标 bool isPlaceOK(int *a, int n, int c) { for (int i = 1; i <= n - 1; ++i) { if (a[i] == c || a[i] - i == c - n || a[i] + i == c + n) return false; //检查位置是否可以放 (n行c列)是将要放置的位置 //a[i] == c如果放在同一列，false //a[i] -+ i = c -+ n 如果在对角线上，（处在同一左(右)对角,行列值只差(和)相同） false } return true; } void printSol(int *a) { for (int i = 1; i <= N; ++i) { //遍历每一行 for (int j = 1; j <= N; ++j) { //遍历每一列 cout << (a[i] == j ? "X" : "-") << " ";; } //如果标记数组中这一行的皇后放在j位置，则输出X，否则输出-， //用空格分隔 cout << endl; //每一行输出一个换行 } cout << endl; //每一组数据一个换行分隔 } void addQueen(int *a, int n) { if (n > N) { //n代表从第一行开始放置 printSol(a); total_cnt++; return ; } for (int i = 1; i <= N; ++i) { //i从第1列到第N列遍历 if (isPlaceOK(a, n, i)) { a[n] = i; //如果可以放置，就把皇后放在第n行第i列 addQueen(a, n + 1); } } } int main() { addQueen(arr, 1); cout << "total: " << total_cnt << " solutions.\n"; return 0; }class Solution { public: vector<vector<string>> ans; bool isHui(string a) { int size = a.size(); for (int i = 0; i < size / 2; i++) { if (a[i] != a[size - i - 1]) return false; } return true; } void find(string s, int index, vector<string> temp) { if (index == s.size()) ans.push_back(temp); for (int i = 1; index + i <= s.size(); i++) { if (isHui(s.substr(index, i))) { vector<string> temp1(temp); temp1.push_back(s.substr(index, i)); find(s, index + i, temp1); } } } vector<vector<string>> partition(string s) { vector<string> temp; find(s, 0, temp); return ans; } };
动态规划 dynamic-programming
动态规划在刷题中经常遇到，有很多种变形题但是基本都是这么个思路，自顶向下 拆分问题 找出状态转移方程。 动态规划就是一种聪明的穷举，记录其中部分过程的状态。非常重要，多做多思考。
- 经典背包问题
#include<stdio.h>
int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a,int b) {
if(a>=b)
return a;
else return b;
}
int KnapSack(int n,int w[],int v[],int x[],int C)
{
int i,j;
//填表,其中第一行和第一列全为0
for(i=0;i<=n;i++)
V[i][0]=0;
for(j=0;j<=C;j++)
V[0][j]=0;
for(i=1;i<=n;i++) {
printf("物品编号%d 重量%d 价值%d ",i,w[i-1],v[i-1]);
for(j=1;j<=C;j++)
{
if(j<w[i-1]) //当前编号物品比整个背包容量还大
{
V[i][j]=V[i-1][j];
printf("[%d][%d]=%2d ",i,j,V[i][j]);
}
else // 用max比较要不要放下当前物品
{
V[i][j]=max(V[i-1][j],V[i-1][j-w[i-1]]+v[i-1]);
printf("[%d][%d]=%2d ",i,j,V[i][j]);
}
}
printf("\n");
}
//判断哪些物品被选中
j=C;
for(i=n;i>=1;i--) {
if(V[i][j]>V[i-1][j]) {
x[i]=1;
j=j-w[i-1];
}
else
x[i]=0;
}
printf("选中的物品是:\n");
for(i=1;i<=n;i++)
printf("%d ",x[i]);
printf("\n");
return V[n][C];
}
void main()
{
int s;//获得的最大价值
int w[15];//物品的重量
int v[15];//物品的价值
int x[15];//物品的选取状态
int n,i;
int C;//背包最大容量
n=5;
printf("请输入背包的最大容量:\n");
scanf("%d",&C);
printf("输入物品数:\n");
scanf("%d",&n);
printf("请分别输入物品的重量:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("请分别输入物品的价值:\n");
for(i=0;i<n;i++)
scanf("%d",&v[i]);
s=KnapSack(n,w,v,x,C);
printf("最大物品价值为:\n");
printf("%d\n",s);
}
- KMP算法 在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。
一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。
阮一峰的博客分析的很好，这里将具体实现分享下。
注意size() 返回的是无符号数，其与负数比较大小时一定要转为有符号的，否则负数会先转变为无符号数之后比较大小结果错误。
#include <iostream>
#include <string>
using namespace std;
const int Maxn = 1024;
class Solution {
public:
int next[Maxn] = { 0 }; //维护p等价前缀长度的记录数组,p匹配失败就跳转到该位置 即匹配了p的个数-1
// 关键在于计算next数组 这里基于最大长度表(字符串的前缀后缀的公共元素的最大长度)来做
// next数组是 除当前字符外 的最长相同前缀后缀。所以为最大长度表向右移一位，初值赋为-1的数组
void GetNextval(string p) {
next[0] = -1;
int i = -1, j = 0; // i表示前缀 j遍历index后缀 求出需要匹配的字符串P的next数组
while (j < int(p.size()) - 1) {
if (i == -1 || p[i] == p[j]) {
++i;
++j;
// next[j] = i; //优化如下所示, 当p[i] == p[j] 时，KmpSearch里不匹配调用next会重复调用，所以这里直接处理
if(p[i] != p[j])
next[j] = i;
else
next[j] = next[i];
}
else
i = next[i];
}
}
int KmpSearch(string s, string p) {
int i = 0, j = 0;
GetNextval(p);
// 注意！ size() 返回的是无符号数，一定要转为有符号的 否则j为-1时会先转变为无符号数比较大小会错误
while ( i < int(s.size()) && j < int(p.size()) ) {
// j为-1 或 匹配成功 s、p的下标都向后走
if (j == -1 || s[i] == p[j]) {
i++;
j++;
}
// 否则字符匹配失败，i不变 j转为next记录值，再用原来的s[i] 与 新的p[j]匹配
// 当j==-1即该字符前不可能有相同前后缀时 还不匹配 说明 i 需要+1 而j=0
else
j = next[j];
}
if (j == p.size())
return i - j;
return -1;
}
};
int main()
{
Solution sol;
string s1, s2;
while (1) {
cin >> s1 >> s2;
cout << sol.KmpSearch(s1, s2) << endl;
}
}
- 关于字符匹配的动态规划题
class Solution {
public:
bool isMatch(string s, string p) {
int sl = s.size(), pl = p.size();
vector<vector<int>> f_map;
f_map.assign(sl + 1, vector<int>(pl + 1, 0));
f_map[0][0] = 1;
// p为正则表达式字符串
// 匿名函数用法 这样做可减少内存的拷贝
auto matches = [&](int i, int j) -> bool{
if(i == 0)
return false;
else if(p[j - 1] == '.')
return true;
else
return s[i - 1] == p[j - 1];
};
for (int i = 0; i <= sl; i++) { // i j代表第几个字符，若为0 表示字符为空
for (int j = 1; j <= pl; j++) { // j为0时除非i=0否则必定匹配失败,初始化时已经给所有除f_map[0][0]外赋0
if(p[j-1] == '*') {
if( matches(i, j-1) )
// f_map[i][j] = f_map[i-1][j]; i-1表示*复制一份前字符，j-2表示*和之前字符代表空
f_map[i][j] = f_map[i-1][j] || f_map[i][j-2]; //加上或，防止当前s头不能减少的情况
else
f_map[i][j] = f_map[i][j-2]; //
}
else{
if( matches(i, j) )
f_map[i][j] = f_map[i-1][j-1];
}
}
}
return f_map[sl][pl];
}
};
class Solution {
public:
// s为输入测试值,测试是否与p匹配 p,包含a-z ? *
// 此题与 10.正则表达式匹配.cpp 类似。不过此处通配符是匹配任意一段字符串，且*前可无字符
// 正则表达式是 *匹配前一个字符N次
bool isMatch(string s, string p) {
int sl = s.size(), pl = p.size();
// dp[i][j] 表示 s的i长度 与 p的j长度 是否匹配 i、j为0表示长度为0的空的字符串
auto match = [&](int i, int j) -> bool {
if (i == 0)
return false; //进入match判断时必定不为* 所以可以直接return false
else if (p[j-1] == '?')
return true;
return s[i-1] == p[j-1];
};
vector<vector<bool>> dp(sl + 1, vector<bool>(pl + 1, false));
dp[0][0] = true;
for (int i = 0; i <= sl; i++) {
for (int j = 1; j <= pl; j++) {
if (p[j-1] == '*')
dp[i][j] = dp[i][j-1] || (i>0 && dp[i-1][j]); //等价 *不存在 或者 *前面匹配成功
else
dp[i][j] = match(i, j) && dp[i-1][j-1];
}
}
return dp[sl][pl];
}
};