Documentation
¶
Overview ¶
Package dynamic is a package of certain implementations of dynamically run algorithms.
Index ¶
- Variables
- func Abbreviation(a string, b string) bool
- func Bin2(n int, k int) int
- func CoinChange(coins []int32, amount int32) int32
- 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) int
- func LongestIncreasingSubsequence(elements []int) int
- func LongestIncreasingSubsequenceGreedy(nums []int) int
- func LpsDp(word string) int
- func LpsRec(word string) 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 Abbreviation ¶
Returns true if it is possible to make a equals b (if b is an abbreviation of a), returns false otherwise
func CoinChange ¶
CoinChange finds the number of possible combinations of coins of different values which can get to the target amount.
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/FridaFino/goalgorithms/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 LongestIncreasingSubsequenceGreedy ¶
LongestIncreasingSubsequenceGreedy is a function to find the longest increasing subsequence in a given array using a greedy approach. The dynamic programming approach is implemented alongside this one. Worst Case Time Complexity: O(nlogn) Auxiliary Space: O(n), where n is the length of the array(slice). Reference: https://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/
func NthCatalanNumber ¶
NthCatalan returns the n-th Catalan Number Complexity: O(n²)
Types ¶
This section is empty.
Source Files