Python 算法教程（33）：数据结构与动态规划

Python 算法 8 小时前 0 0

数据结构详解

数据结构是算法的基石。

链表

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

栈和队列

stack = []
stack.append(1)  # 压栈
stack.pop()      # 出栈

from collections import deque
queue = deque()
queue.append(1)  # 入队
queue.popleft()  # 出队

动态规划

def fib_dp(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

背包问题

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(capacity+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

掌握数据结构，算法不再难！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。