Dynamic Programming is not Black Magic

• codility

  1 2 10.0 JavaScript

  Codility Lessons (by dsego)

I remember learning about the knapsack problem and trying out recursive ways to solve it as well.

https://github.com/dsego/codility/blob/main/knapsack.js

• zdps

  1 3 2.3 Zig

  dps calculations accounting for overkill

I think their point is that naive caching attempts still result in duplicate work, and if you start by viewing the problem recursively then DP is a clever insight allowing you to avoid that duplicate work. You're right; it's not _just_ function calling overhead or anything minor; it often represents major Big-O improvements. I think that's in alignment with what they're saying.

I like your insight about Fibonacci needing less state than a naive DP would suggest. Diving into that a bit, DP implementations represent a DAG. More importantly, for all the problems that easily fit into DP that DAG has small numbers of "local" connections -- you can partition it into at least O(some_meaningful_dimension) many topologically sorted levels where each level only depends on a small, known, finite number of previous levels (often 1-2), not deeper DAG nodes. A clever choice of order of operations then looks for a min-cut on that graph, proceeding through those levels. Fib has at most O(n) levels and at least O(n) state for naive DP, so a clever implementation has O(n/n)=O(1) state. Edit distance has at most O(n) levels and at least O(n^2) state, so a clever implementation has O(n^2/n)=O(n) state. I did something similar for some DP probability calculation [0], and it reduces state from quadratic to linear.

Fibonacci is, slightly pedantically, one of the worst algorithms to analyze this way. Only the smallest inputs actually fit in machine integers, and the exponential increase in the size of any bigints involved really puts a damper on a naive Big-O analysis. Fib mod 2^64 (or some biggish prime) fits into the spirit of things better.

[0] https://github.com/hmusgrave/zdps

• InfluxDB

  www.influxdata.com featured

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• Fibonacci-Sequence

  16 1 1.2 Python

  Application that calculates the number that is located in the selected position. Made with Python and Tkinter library.

Suggest a related project