递归

利用递归可以简化代码,提高运算速度(quickSort)

函数或者方法自己调用自己,每次调用传入不同的变量,有助于编程者解决复杂问题

如n皇后问题,汉诺塔,阶乘问题,迷宫问题,球和篮子的问题;栈解决的问题

查看代码

原则

1. 执行一个函数时, 就创建一个新的受保护的栈空间(新函数栈)
2. 函数的局部变量是独立的,不会相互影响,如果希望各个函数使用同一个数据,使用引用传递
3. 递归必须向递归的条件逼近,否则就会无限递归,就死龟了
4. 当函数指向完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同事当函数执行完毕或者返回时,
该函数就会被系统销毁.

• 迷宫问题

• 表达式求值问题

• 爬楼梯问题

n级台阶走法,每次走1级台阶或者2级台阶.(分步走,第一步有两种情况)

n级台阶的走法=
先走一级后，n-1级台阶的走法+
先走两级后，n-2级台阶的走法

f(n) = f(n-1) + f(n-2)
边界条件:
f(1) = 1 
f(2) = 2  

• 放苹果问题

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，
问共有多少种不同的分法？5，1，1和1，5，1 是同一种分法。

N>M, f(M,N) == f(M,M) ,有N-M个空盘;
N<=M, 总放法= 有盘子为空+ 没有盘子为空的放法
f(M,N) == f(M,N-1) + f(M-N,N)  //m和n是如何变化的
M=0,没有苹果的时候,不放苹果也为一种放法,1
N=0,找不到盘子,找不到方法,0

• 算24

给出4个小于10个正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。
现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。
这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。
比如，对于5，5，5，1，我们知道5 * (5 –1 / 5) = 24，因此可以得到24。
又比如，对于1，1，4，2，我们怎么都不能得到24.

问题分解
问题规模减少
1. 先拿两个数进行运算.运算的结果,和剩余的n-2个数,构成了n-1个数求24的问题.
边界条件, n=1时, 判断是不是等于24

动态规划

原理

动态规划与分治法类似，都是把大问题拆分成小问题，
通过寻找大问题与小问题的递推关系，解决一个个小问题，
最终达到解决原问题的效果。
但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，
而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，
在新问题里需要用到的子问题可以直接提取，避免了重复计算，
从而节约了时间，所以在问题满足最优性原理之后，
用动态规划解决问题的核心就在于填表，表填写完毕，
最优解也就找到。

最优性原理是动态规划的基础，
最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：
不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，
其后各阶段的决策序列必须构成最优策略”。

数字三角形

• 问题描述:

{7},
{3, 8},
{8, 1, 0},
{2, 7, 4, 4},
{4, 5, 2, 6, 5},
在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为0 -99

• 思路

用二维数组存放数字三角形。
D( r, j)   : 第r行第j 个数字(r,j从1开始算)
MaxSum(r, j) :   从D(r,j)到底边的各条路径中，最佳路径的数字之和。
问题：求MaxSum(1,1)
典型的递归问题。
D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。

故对于N行的三角形：

if  r == N    {
	MaxSum(r,j) = D(r,j)
} else {
	MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)
}

最长公共子序列问题

问题描述

给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致

• 思路

输入两个串s1,s2,
    设MaxLen(i,j)表示:  s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算）
    MaxLen(i,j) 就是本题的“状态”
    假定len1 = strlen(s1),len2 = strlen(s2）
    那么题目就是要求MaxLen(len1,len2)
    显然：
    MaxLen(n,0)  = 0  ( n= 0...len1）
    MaxLen(0,n)  = 0  ( n=0...len2）递推公式：
    if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]
        MaxLen(i,j) = MaxLen(i-1,j-1) + 1
    else
        MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) )

• 证明

S1,S2表示表示长度为i,j的序列
S1[I-1]表示长度为i-1的序列
S2[J-1]表示长度为j-1的序列
S1[i-1]表示S1的第i-1个字符
S2[j-1]表示S2的第j-1个字符

在S1[i-1] != S2[j-1]情况下:
MaxLen(S1,S2)不会比MaxLen(S1,S2[J-1])和MaxLen(S1[I-1],S2)两者之中任意一个小,也不会比两者都大.
	证明:
采用反证法:
    若MaxLen(S1,S2) 比 MaxLen(S1,S2[J-1])和MaxLen(S1[I-1],S2) 都大,
    情况1: MaxLen(S1,S2) > MaxLen(S1,S2[J-1]
    则,S1[i-1] 必定是 MaxLen(S1,S2)的子序列的关键元素,且为最后一个元素.
    同理:S2[j-1] 必定是 MaxLen(S1,S2)的子序列的关键元素,且为最后一个元素.
    故而S1[i-1]==S2[j-1],
    与假设矛盾,从而假设不成立. 证毕~

背包问题

• 问题描述:

	有N件物品和一个容积为M的背包。第i件物品的体积w[i]，价值是d[i]。
	求解将哪些物品装入背包可使价值总和最大。
	每种物品只有一件，可以选择放或者不放(N<=3500,M <= 13000)。

• 思路:

	用F[i][ j] 表示取前i种物品，使它们总体积不超过j的最优取法取得的价值总和。要求F[N][M]
	边界条件:
	if w[1] <= j {
		F[1][j] = d[1]
	} else {
		F[1][j] = 0
	}

	F[i][j] = max { F[i-i][j], F[i-1][j-w[i]] +d[i]}

• 思考:

	本题如用记忆型递归，需要一个很大的二维数组，会超内存。
	注意到这个二维数组的下一行的值，只用到了上一行的正上方及左边的值，
	因此可用滚动数组的思想，只要一行即可。即可以用一维数组，用“人人为我”递推型动归实现。