什么是动态规划

从斐波那契数列

递归

1
2
3
4
5
6
def fabinaac(n):
    if n==1 or n==2:
        return 1
    else:
        return fabinaac(n-1)+fabinaac(n-2)
print(fabinaac(5))

但是递归要解决的子问题太多了，低效。

非递归，递推版

1
2
3
4
5
6
7
def fabinacc2(n):
    f = [0,1,1]
    if n>2:
        for i in range(n-2):
            num = f[-1]+f[-2]
            f.append(num)
    return f[n]

动态规划: 递推式+重复子问题

钢条切割问题

image-20230326135701190

image-20230326140853754

Python接受数据的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1、接收一个元素
s = input() #字符串
n = int(input()) #整数

2、接收两个或三个元素（以空格隔开）
n, m = map(int, input().split())
n, m, k = map(int, input().split())

3、将一行元素放入数组中
num = [int(i) for i in input().split()]

4、将数组变为整个字符串
s= "".join(map(str,num))

Python的内置方法

1
2
3
4
5
6
7
hex()  将数字转换为十六进制字符串
oct()  将整数转换成八进制字符串               
oct(int("39",16)) >>>'0o71'  十六进制转八进制
chr(number)  返回数字对应的ascii码值
ord(number)  返回数字对应的字母
divmod(a,b)  返回(a//b,a%b)

Python模块

collections模块

1
2
3
4
5
6
7
8
9
10
11
1、collections.deque([])
        q = collections.deque([1, 2, 3, 4])
        q.rotate(1)
        print(q)  # [4, 1, 2, 3]
        q.rotate(1)
        print(q)  # [3, 4, 1, 2]
2、collections.Counter()
    >>> import collections
    >>> collections.Counter([1,2,3,1,2,3,1,2])
    Counter({1: 3, 2: 3, 3: 2})

datetime模块

1、日期增加

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

>>> import datetime
>>> bt = datetime.date(2000,11,6)
>>> print(bt)
2000-11-06
>>> a = datetime.timedelta(days=100)
>>> a
datetime.timedelta(days=100) #weeks / hours
>>> b = a + bt
>>> b
datetime.date(2001, 2, 14)

2、给定日期求星期

1
2
3
bt.weekday()：返回weekday，如果是星期一，返回0；如果是星期2，返回1，以此类推；
bt.isoweekday()：返回weekday，如果是星期一，返回1；如果是星期2，返回2，以此类推；

3、返回公元公历开始到现在的天数

1
2
3
>>> bt.toordinal()
730430

calendar模块

1
2
3
4
5
6
7
8
 1、判断是否为闰年
 >>> import calendar
 >>> calendar.isleap(2022)
 False

2、返回两年之间的闰年总数
 >>> calendar.leapdays(2000,2020)