Archive for the “Dynamic Programming” category
Traveling on a Grid
by David Liu on October 6, 2008
You’re traveling from the top-left corner of a grid (0,0) to the bottom-right cell of a NxM grid. N and M are between 0 and 250. Entering each cell has a cost. At each step, you can only move down (…)
Fibonacci – Solutions
by David Liu on October 6, 2008
The recursive implementation is based directly on the mathematical definition of the Fibonacci function. // Naive, recursive implementation (slow!) public int fib(int n) { if (n <= 0) return 0; if (n == 1) return 1; return fib(n-1) + fib(n-2); (…)
Introduction to Dynamic Programming: Fibonacci
by David Liu on September 28, 2008
Here are some problems to think about before our next meeting. The Fibonacci sequence is defined as a sequence where each value is the sum of the two previous values. The first value is defined to be 0, and the (…)