Programação Dinâmica (Dynamic Programming)

A programação dinâmica é uma técnica de otimização de algoritmos que resolve problemas que podem ser divididos em subproblemas sobrepostos e, em seguida, armazena os resultados desses subproblemas para evitar recálculos redundantes. Ela é especialmente útil para problemas de otimização, como encontrar o caminho mais curto em um grafo, a subsequência comum mais longa, entre outros.

Heap

Um heap é uma estrutura de dados do tipo árvore, com uma propriedade adicional: para cada nó i exceto o nó raiz, o valor armazenado no nó é maior ou igual ao valor armazenado no pai (para um "heap máximo") ou menor ou igual ao valor armazenado no pai (para um "heap mínimo"). Isso faz com que o elemento mais alto ou mais baixo do heap, dependendo do tipo de heap, esteja sempre no topo, permitindo operações eficientes de inserção, remoção e acesso ao máximo ou mínimo.

Fila de Prioridade

Uma fila de prioridade é uma abstração de uma estrutura de dados que permite inserir elementos junto com uma "prioridade" associada e remover o elemento com a maior ou menor prioridade (dependendo do tipo de fila de prioridade). Geralmente, é implementada usando um heap para permitir acesso eficiente ao elemento prioritário.

Programação Dinâmica

Aqui está um exemplo simples de como usar programação dinâmica para calcular o n-ésimo número de Fibonacci:

            
            package main

            import "fmt"

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

            func main() {
                fmt.Println("Fibonacci de 6:", fibonacci(6))
            }

            
         

Heap (Fila de Prioridade):

Aqui está um exemplo de como usar um heap como fila de prioridade em Go:

          
            package main

            import (
                "container/heap"
                "fmt"
            )

            type IntHeap []int

            func (h IntHeap) Len() int           { return len(h) }
            func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
            func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

            func (h *IntHeap) Push(x interface{}) {
                *h = append(*h, x.(int))
            }

            func (h *IntHeap) Pop() interface{} {
                old := *h
                n := len(old)
                x := old[n-1]
                *h = old[0 : n-1]
                return x
            }

            func main() {
                h := &IntHeap{2, 1, 5}
                heap.Init(h)
                heap.Push(h, 3)
                fmt.Printf("Mínimo: %d\n", (*h)[0])
                for h.Len() > 0 {
                    fmt.Printf("%d ", heap.Pop(h))
                }
            }

          
        

Este é um exemplo simples que demonstra como usar um heap como fila de prioridade para armazenar inteiros.