def move(index, start, mid, end):

# index: 表示有几个圆盘，start： 开始搬运的塔座 mid：中间的塔座，end：需要搬到的目的塔座

# 记忆方法: 上面的兄弟先搬到中间，上面的兄弟再从中间搬回来，大兄弟(第一个兄弟)就结束了

   if index == 1:

       # index=1表示 第一个兄弟结束

       print(f'{start}-->{end}')

       return

   else:

       move(index-1, start, end, mid) # 上面的兄弟搬到中间塔座

       # 四个参数index-1(上面的兄弟), start, end, mid, 记住这个顺序，搬回来只是把mid这个参数移到最前面了

       print(f'{start}-->{end})

       move(index-1, mid, start, end)  # 上面的兄弟从中间塔座搬回来

move(5, 'A', 'B', 'C')

感悟：

首先定义函数的功能，功能与某个序号进行关联，然后进行抽象。

得到递归过程~~~

递归不是算法，是一个技术站，回溯法，动态规划，分治法 这些算法，可能会用到递归这个技术站

通过不同的题目理解同一个算法

回溯:

1. 设置现场

2. 开始递归

3. 恢复现场
   

重点：合理设计递归函数

from collections import defaultdict

total = defaultdict(int)

...

total[k] += 1

#使用动态规划求解0-1背包问题
info = [
    [3, 8],
    [2, 5],
    [5, 12]
]
total = 5
# 老三初始化
pre_max = []
for _ in range(info[-1][0]):
    pre_max.append(0)
for _ in range(info[-1][0], total+1):
    pre_max.append(info[-1][1])

for k in range(len(info)-2, -1, -1):
    new_pre_max = []
    for i in range(total+1):
        value_list = []
        if i >= info[k][0]:
            value_list.append(info[k][1] + pre_max[i-info[k][0]])
        value_list.append(pre_max[i])
        new_pre_max.append(max(value_list))
    pre_max = new_pre_max

print(pre_max)

老师视频讲的写两重for，我的执行结果还是原来二维列表里的值，写成一个函数就对了。

pyramid = [
             [13],
             [11, 8],
             [12, 7, 26],
             [6, 14, 15, 8],
             [12, 17, 13, 24, 11]
          ]

def search(depth):
    while depth >= 1:
        for j in range(0, depth):
            pyramid[depth - 1][j] += max(pyramid[depth][j], pyramid[depth][j + 1])
        print(pyramid[j])
        depth -= 1
    
search(4)

递归斐波那契数列

什么是递归

  什么是递归

def fib_test2(k):
    """
    求解第k个数的值
    """
    assert k > 0, "k必须大于0"
    if k in [1, 2]:
        return 1

    k_1 = 1
    k_2 = 1
    for i in range(3, k+1):
        k_2, k_1 = k_1, k_2 + k_1
    return k_1

动态规划法

多阶段决策

爬楼梯问题：

假设你正在爬楼梯，楼梯有n级，每次你只能爬1级或者2级，那么你有多少中方法爬到楼梯的顶部？

不用关心以前是怎么走的，到顶楼最后一步只有两种情况，一种是迈2步，一种是迈1步；迈一步的情况加上迈两步的情况就是一共有多种方法。

2、生兔子问题

有一对兔子，从出生后第3个月起每个月都一对兔子，小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死

第一个  1对兔子

第二个   1+0对兔子

第三个    1+1对兔子

第四个    1+1+1对兔子

第五个     1+1+1+1+1对兔子

f(n) = f(n-1)+f(n-2)

斐波拉契数列：

1、斐波拉契数列又称黄金分割数列，因为数学家斐波拉契衣以兔子繁殖为例子而引入，故又称为兔子数列

2、指的是这样一个数列：1、1、2、3、5、8、13、21、34、.....后面的数都等于前面的数的和。

# 递归的两个要素
# 1、什么地方递归调用本身
# 2、什么时候终止递归
# 1 1 2 3 5 8 13


def fib_test(k):
    """递归就是自己调用自己"""
    # 求解第k个数的值
    # 在这里终止递归
    if k in [1, 2]:
        return 1
    # 调用递归
    return fib_test(k-1) + fib_test(k-2)


if __name__ == "__main__":
    print(fib_test(7))

什么是递归

1、递归的学习最好不要似是而非，能弄懂内在过程很重要

2、递归不是算法，但是用途却很大

3、递归的定义：函数内部调用函数本身。

4、递归这种技术在很多算法中都存在：回溯法、动态规划、分治法等

1、递归分为两个过程：递、归，这些都是自动完成的。

2、递归一定要终止，怎么写终止条件很重要。

defaultdict 如果找不到，返回一个int，赋值0

<?php

function er($val){

$info=[1,2,4,5,6,7,8,9,22,33,44,55,66,77];

$start = 0;

$end = count($info);//14

while($start<$end){

$mid=ceil(($end-$start)/2);//3

if($info[$mid+$start]==$val){

return $start+$mid;

}elseif($info[$mid+$start]<$val){

$start = $start + $mid;

}else{

$end = $end - $mid;

}

}

return "没找到";

}

echo er(8);