动态规划DP

动态规划（Dynamic Programming，简称DP）是一种常用于解决优化问题的算法技巧。DP算法通常用于解决那些可以被分解成子问题，并且子问题的解可以被重复使用以构建更大问题的情况。下面我将提供一些从易到难的DP算法示例，以帮助你逐步学习。

1. 斐波那契数列

斐波那契数列是最简单的DP问题之一。它可以用递归方式来计算，但递归效率低下，DP可以通过记忆化搜索来提高效率。

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

package main

import "fmt"

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

func main() {
    fmt.Println(fibonacci(10)) // 输出：55
}

2. 最长上升子序列（Longest Increasing Subsequence，LIS）

LIS问题是在一个序列中找到一个最长的子序列，该子序列满足元素递增的条件。

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

package main

import (
    "fmt"
)

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    maxLen := 1

    for i := 0; i < len(nums); i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        maxLen = max(maxLen, dp[i])
    }

    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
    fmt.Println(lengthOfLIS(nums)) // 输出：4
}

3. 背包问题

背包问题是一个经典的DP问题，有多个变种。最基本的背包问题是0/1背包问题，其中有一定容量的背包和一组物品，每个物品都有重量和价值，目标是选择一组物品放入背包中，使得它们的总重量不超过背包容量，同时总价值最大化。

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

package main

import (
    "fmt"
)

func knapsack(values, weights []int, capacity int) int {
    n := len(values)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= capacity; j++ {
            if weights[i-1] <= j {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    return dp[n][capacity]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    values := []int{60, 100, 120}
    weights := []int{10, 20, 30}
    capacity := 50
    fmt.Println(knapsack(values, weights, capacity)) // 输出：220
}

4. 最短路径问题

最短路径问题涉及找到两个节点之间的最短路径。一个常见的例子是Dijkstra算法，它用于在带权重图中找到单源最短路径。

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

package main

import (
    "container/heap"
    "fmt"
)

type Graph map[string]map[string]int

func dijkstra(graph Graph, start string) map[string]int {
    distances := make(map[string]int)
    for node := range graph {
        distances[node] = int(^uint(0) >> 1) // 初始化距离为无穷大
    }
    distances[start] = 0

    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Item{value: start, priority: 0})

    for pq.Len() > 0 {
        current := heap.Pop(&pq).(*Item).value
        for neighbor, weight := range graph[current] {
            distance := distances[current] + weight
            if distance < distances[neighbor] {
                distances[neighbor] = distance
                heap.Push(&pq, &Item{value: neighbor, priority: distance})
            }
        }
    }

    return distances
}

type Item struct {
    value    string
    priority int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func main() {
    graph := Graph{
        "A": {"B": 1, "C": 4},
        "B": {"A": 1, "C": 2, "D": 5},
        "C": {"A": 4, "B": 2, "D": 1},
        "D": {"B": 5, "C": 1},
    }

    distances := dijkstra(graph, "A")
    fmt.Println(distances) // 输出：map[A:0 B:1 C:3 D:4]
}

以上是从简单到复杂的一些动态规划示例，你可以根据自己的学习进度逐步深入学习这些示例，并尝试解决更复杂的DP问题。希望这些示例能帮助你入门动态规划算法！

作者: 东南dnf

链接: https://dnf.doyi.online/posts/2029676213.html

声明: 本博客所有文章除特别声明外，均采用许可协议 CC-BY-NC-4.0 转载请注明出处！

算法

目录

动态规划DP

1. 斐波那契数列

2. 最长上升子序列（Longest Increasing Subsequence，LIS）

3. 背包问题

4. 最短路径问题