Documentation
¶
Overview ¶
Package dynamic is a package of certain implementations of dynamically run algorithms.
Index ¶
- Variables
- func Bin2(n int, k int) int
- func CutRodDp(price []int, length int) int
- func CutRodRec(price []int, length int) int
- func EditDistanceDP(first string, second string) int
- func EditDistanceRecursive(first string, second string, pointerFirst int, pointerSecond int) int
- func IsSubsetSum(array []int, sum int) (bool, error)
- func Knapsack(maxWeight int, weights, values []int) int
- func LongestCommonSubsequence(a string, b string, m int, n int) int
- func LongestIncreasingSubsequence(elements []int) int
- func LpsDp(word string) int
- func LpsRec(word string, i, j int) int
- func MatrixChainDp(D []int) int
- func MatrixChainRec(D []int, i, j int) int
- func Max(a, b int) int
- func NthCatalanNumber(n int) (int64, error)
- func NthFibonacci(n uint) uint
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrInvalidPosition = fmt.Errorf("invalid position in subset")
var ErrNegativeSum = fmt.Errorf("negative sum is not allowed")
Functions ¶
func EditDistanceDP ¶
EditDistanceDP is an optimised implementation which builds on the ideas of the recursive implementation. We use dynamic programming to compute the DP table where dp[i][j] denotes the edit distance value of first[0..i-1] and second[0..j-1]. Time complexity is O(m * n) where m and n are lengths of the strings, first and second respectively.
func EditDistanceRecursive ¶
EditDistanceRecursive is a naive implementation with exponential time complexity.
func Knapsack ¶
Knapsack solves knapsack problem return maxProfit
Example ¶
package main
import (
"fmt"
"github.com/TheAlgorithms/Go/dynamic"
)
func main() {
fmt.Print(dynamic.Knapsack(10, []int{4, 5, 8}, []int{50, 15, 60}))
}
Output: 65
func LongestCommonSubsequence ¶
LongestCommonSubsequence function
func LongestIncreasingSubsequence ¶
LongestIncreasingSubsequence returns the longest increasing subsequence where all elements of the subsequence are sorted in increasing order
func NthCatalanNumber ¶
NthCatalan returns the n-th Catalan Number Complexity: O(n²)
Types ¶
This section is empty.
Source Files