简单算法——回溯、贪心、动态规划

void backtracking(参数){
if(终止条件){叶子节点收集结果;
return ;}
for(集合元素集){
处理节点;
递归;
回溯操作;//执行到此步说明此次循环递归已经找到一个结果，
                 //需要回溯来找新的结果
return;}
}
1
2
3
4
5
6
7
8
9
10

二维数组result用于保存结果
一维数组path用于记录组合
void backtracking（n,k,startindex）{//n个数，k长度，当前起始位置index
if(path.size==k){//叶子节点，找到结果
result.push(path);
return;}
for(int i=startindex;i<=n;i++){
path.push(i);//装入一个元素
backtracking(n,k,i+1);//递归得到一个结果
path.pop();//弹出元素，进行回溯
1
2
3
4
5
6
7
8
9
10

设置三维数组result用于存储结果;
void backtarcking(chessboard,n,row){//n*n的棋盘，当前放置位置为第row行
if(row==n){//说明到了叶子节点，保存结果
result.pushback(chessboard);
return ;}
for(int i=0;i

//胃口g 1，2，7，10
//饼干s 1，3，5，9
sort(g);sort(s)//把饼干和胃口数组先从小到大排序，便于比较
int result=0;
int index=s.size()-1;
for(i=g.size()-1;i>=0;i--){
while(index>=0&&s[index]>=g[i]){//使用while便于控制条件，
 //饼干大于胃口成功投喂，判断index需大于0
result++;
index--;
}}
return result
1
2
3
4
5
6
7
8
9
10
11
12

s=ababcdacadefegde;//一个区间为ababcdaca，另一个为defegde，
                                      //第一个区间包含所有abc，第二个包含所有defg
                                    //输出[9,7]
1
2
3

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
a  b  a  b  c  b  a  c  a  d  e   f    e   g   d   e 
8  5  8  5  7  5  8  7  8  14 15 11 15 13 14 15   最后出现位置
1
2
3

int hash[27]={0};
for(i=0;i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

贪心总结

思想很简单，局部到整体，但是有时候要借助创建的变量和方法确实难以想到，所以难点在于辅助的构造，而非算法本身。

动态规划

用于解决重叠子问题很多的问题，当前的每个状态都有上一个状态推导而来，可以说是大型的递归，我理解是在在运行中变化生成结果数组或者结果矩阵，故而称为动态规划。与贪心不同，贪心只是单纯地根据先有情况选出最优，而动态规划是需要推导得到最好结果。

一般流程

设置dp数组也就是结果集并搞懂dp[i]下标含义；
找到dp数组递推公式，即找到子问题的通解公式；
dp数组的初始化，具体问题具体分析；
确定遍历顺序；
输出打印dp数组，便于调试。

斐波那契数列

每个数为前两个数之和，求第n个数，以1，1开始。
直接递归或者单纯简单for循环

sum=dp[0]+dp[1];
dp[0]=dp[1];
dp[1]=sum;
1
2
3

就可以求，但是还是从简单问题理清思路，熟悉解决问题的一般流程。
dp[i]表示第i个数的值；
递推公式：dp[i]=dp[i-1]+dp[i-2]
数组初始化，dp[0]=1,dp[1]=1
遍历顺序从前至后，伪代码如下：

vector dp(n+1);
dp[0]=1;dp[1]=1;
for(i=2;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
return dp[n];
1
2
3
4
5

01背包

不同物品不同价值，背包最多能装的价值。
物品 0 1 2
重量 1 3 4
价值15 20 30 背包最大重量为4
首先可以使用暴力法，通过回溯列举所有可能性，每个物品取或者不取，复杂度为2的n次方。
dp数组含义： 使用动态规划是设置二维数组dp[i][j]，代表[0,i]之间的物品，任意取放到容量为j的背包里的最大价值，不放物品i时的最大价值为dp[i-1][j]，放了物品i的价值为dp[i-1][j-weight[i]]+value[i]。
递推公式： 解释一下就是根据物品，每次更新对比当前物品放进背包前后价值大小，取最大值，与贪心有点类似，但是贪心只会拿着大的就往包里塞，而动态规划则是边拿边算，如果当前价值更大就把前边放的乱七八糟东西拿出来，递推公式为
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]
dp数组初始化： 二维表格可初始化如下:

ij		0		1		2		4		5 
0		0		15	15	15	15
1		0	
2		0
1
2
3
4

回顾对dp的定义：在i内任意取物品放到容量为j的价值，表格内现为已知元素，其余需要计算的元素如何定义呢？由递推式可知，每个元素都由上一层元素计算得来，故每次计算都会赋值且在计算之前与其他元素无关，初始化可任意。
遍历顺序：

for(物品）｛
for(背包容量）
递推公式｝
1
2
3

即二维数组先填行数据，该遍历顺序由递推公式决定，因为当前元素要一来上一行元素。

滚动数组

用二维数组来解决01背包是一种比较基础的方法，但是该解空间有太大冗余，其实也可以压缩状态转而采用一维数组。
因为当前层是由上一层推导而来，如果我们将上一行拷贝到当前行，是不是就能将矩阵压缩成一行，而在过程中数组不断更新覆写，好像在向前滚动，故而称为滚动数组。

最长连续递增子序列

含义如题，例如1 3 5 4 7 序列输出3。
dp[i]表示以i为结尾的最长连续递增子序列长度。
因为只看连续，所以只需要比较dp[i]与dp[i-1]的大小即可，递推公式代码表示如下：

if(numb[i]>num[i-1]
dp[i]=dp[i-1]+1;
1
2

所有dp初始化为1；
遍历顺序从前向后
for(i=1;i
收集结果
if(dp[i]>result) result=dp[i]