Struct DynamicProgramming 

pub struct DynamicProgramming;

A collection of classic dynamic programming algorithms.

Implementations

impl DynamicProgramming

pub fn knapsack(capacity: usize, weights: &[usize], values: &[usize]) -> usize

0/1 knapsack: maximum value achievable with given capacity.

pub fn longest_common_subseq(s1: &[u8], s2: &[u8]) -> usize

Length of the longest common subsequence of byte slices s1 and s2.

pub fn matrix_chain_order(dims: &[usize]) -> usize

Minimum number of scalar multiplications to compute a chain of matrices.

dims has length n+1 where the i-th matrix is dims[i] × dims[i+1].

pub fn coin_change(coins: &[usize], amount: usize) -> Option<usize>

Minimum number of coins from coins that sum to amount.

Returns None if no solution exists.