发表于

递归：

递归定义：

一种直接或者间接调用自身函数或者方法的算法，本质就是把问题分解成规模缩小的同类子问题，递归调用方法表示问题的解。

递归特点：

1.一个问题的解可以分解为几个子问题的解
2.问题与分解后的子问题，解决思路完全一样
3.存在递归出口，即存在明确的递归结束条件

举例：爬台阶问题

问题描述：一个人爬楼梯，一次只能爬一个或两个台阶，假设t一共有n个台阶，共有多少种不同的爬楼梯方法？

思路： 根据第一次的走法，可以把问题分为两类：
1. 第一步走了1个台阶，后面是 n-1 个台阶的走法
2. 第一步走了2个台阶，后面是 n-2 个台阶的走法
递归公式：
f (n) = f (n-1) + f (n-2)
递归出口：
f (1) = 1
f (2) = 2 #问题不可分
递归代码：
int f ( n):
if n==1: return 1
if n==2: return 2
return f (n-1) +f (n-2)

动态规划

三个重要概念：

​ 最优子结构
​ 边界
​ 状态转移方程
​

动态规划相关问题：

斐波那契数列：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39

思路：$f\left ( n \right )=\left{\begin{matrix}
0, n=0 & \
1,n=0& \
f(n-1)+f(n-2), n>1&
\end{matrix}\right.$

递归是将一个问题划分为多个子问题求解，动态规划也是，但是动态规划会将子问题缓存起来，从而避免重复求解子问题。

递归：

1
2
3
4
5
6
7
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n==0:return 0
        if n==1: return 1
        return self.Fibonacci(n-1)+self.Fibonacci(n-2)

动态规划：

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        temp = [0,1]
        while len(temp)<=n:
            temp.append(temp[-1]+temp[-2])
        return temp[n]

矩形覆盖：

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

思路：问题本质是斐波那契数列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number <=0:
            return 0
        if number<=2:
            return number
        else:
            a=1
            b=1
            for i in range(number):
                a,b = b,a+b
            return a

二进制中1的个数：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：与n-1做and 操作，直到为0，操作的次数就是1的个数。

1
2
3
4
5
6
7
8
9
10
11
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count=0
        if n<0:
            n=n & 0xffffffff
        while n:
            n = n & (n-1)
            count+=1
        return count

丑数：

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路：丑数应该是另一个丑数乘以2，3，或者5的结果。重要的是大小顺序，所以我们从丑数✖️2，3，5中的值中选择最小的，被选择的要记下位置更新。用3个index来分别记录位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:
            return 0
        uglylist=[1]
        indextwo = 0
        indexthree = 0
        indexfive = 0
        for i in range(index-1):
            newugly = min(uglylist[indextwo]*2, uglylist[indexthree]*3, uglylist[indexfive]*5)
            uglylist.append(newugly)
            if (newugly%2==0):
                indextwo +=1
            if (newugly%3==0):
                indexthree +=1
            if (newugly%5 ==0):
                indexfive +=1
        return uglylist[-1]