北航数据结构笔记系列六

桃木山人

于 2023-02-20 17:03:25 发布

阅读量164

点赞数 1

分类专栏：数据结构课程笔记文章标签：数据结构 python 开发语言 CSDN开发云编辑器

本文链接：https://blog.csdn.net/CSDN_WHO/article/details/129127834

版权

数据结构课程笔记专栏收录该内容

9 篇文章

订阅专栏

文章介绍了如何使用枚举法和动态规划解决计算机科学中的问题，如查找阿姆斯特朗数，计算字母算数最少线连接所有点的最大连续子序列，以及01背包问题的解决方案。通过优化的枚举法减少了计算时间，动态规划则用于找到最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

11.10课程 BUAA ASE数据结构课程

文章目录

1.枚举法-->动态规划

1.枚举法–>动态规划

阿姆斯特朗数

#把int先转成str
for i in range(99,9999999):
    a=list(map(int,str(i)))
    sum=0
    for j in a:
        sum+=j**len(a)
    if sum==i:
        print(i)
#优化，增加sum>i跳出
for i in range(99,9999999):
    a=list(map(int,str(i)))
    sum=0
    for j in a:
        sum+=j**len(a)
        if sum>i:
            break
    if sum==i:
        print(i)

字母算数
最少线连接所有点

最大连续子序列

#  状态转移方程：MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]}
a=list(map(int,input().split()))
sum=0
result=0
for i in a:
    sum+=i
    result=max(sum,result)
    if sum<0:
        sum=0
print(result)

01背包问题

V(i,j)=V(i-1,j)     无法再放入
V(i,j)=max(V（i-1,j) ,  V(i-1,j-wi)+v(i))   可以再放入
tian'x