Dynamic Programming with Memoization
Dynamic Programmingintermediate~8 min
Solve overlapping-subproblem problems efficiently by storing intermediate results in arrays.
Step 1 — Fibonacci via DP
The naive recursive Fibonacci runs in O(2^n). DP stores each result so every sub-problem is solved exactly once, giving O(n) time.
n = 20; fib = zeros(1, n); fib(1) = 1; fib(2) = 1; for i = 3:n fib(i) = fib(i-1) + fib(i-2); end disp(fib)▶ Run in SimLab
Expected output: Sequence starting 1 1 2 3 5 8 … ending at 6765
Step 2 — Visualise growth
Fibonacci numbers grow exponentially. A semilogy plot makes this clear and lets you verify the golden-ratio doubling.
n = 20;
fib = zeros(1, n);
fib(1) = 1; fib(2) = 1;
for i = 3:n
fib(i) = fib(i-1) + fib(i-2);
end
semilogy(1:n, fib);
xlabel('n'); ylabel('F(n) (log scale)');
title('Fibonacci Growth')▶ Run in SimLabExpected output: Straight line on a log-scale plot confirming exponential growth
Step 3 — 0/1 Knapsack
The knapsack problem: given items with weights and values, maximise value within a weight budget. Build a 2D DP table where dp(i, w) = max value using first i items with capacity w.
weights = [2 3 4 5];
values = [3 4 5 6];
W = 8;
n = length(weights);
dp = zeros(n+1, W+1);
for i = 1:n
for w = 1:W
dp(i+1, w+1) = dp(i, w+1);
if weights(i) <= w
take = dp(i, w-weights(i)+1) + values(i);
if take > dp(i+1, w+1)
dp(i+1, w+1) = take;
end
end
end
end
printf('Max value: %d\n', dp(n+1, W+1))▶ Run in SimLabExpected output: Max value: 10
Related Tutorials
Try SimLab — Free MATLAB® Alternative
466 functions. Runs in your browser. No install.
Open SimLab