Dynamic Programming in C
Subject: Data Structures and Algorithms · Language: C · Level: intermediate · 6 min read
Understand dynamic programming with overlapping subproblems, optimal substructure, memoization, and tabulation.
Dynamic Programming, usually called DP, is a problem-solving technique used when a problem can be broken into smaller repeated subproblems.
Instead of solving the same subproblem again and again, DP stores the answer and reuses it later. This saves time and makes many difficult problems efficient.
Why DP Is Important
DP is very common in coding interviews and competitive programming. It is used in problems related to sequences, choices, paths, optimization, counting, and partitioning.
Examples include Fibonacci, climbing stairs, coin change, knapsack, longest common subsequence, edit distance, matrix path problems, and many more.
When Can We Use DP?
A problem is usually suitable for DP when it has two properties: overlapping subproblems and optimal substructure.
Overlapping Subproblems
Overlapping subproblems means the same smaller problem appears many times.
For example, in recursive Fibonacci, `fib(5)` needs `fib(4)` and `fib(3)`. Then `fib(4)` again needs `fib(3)` and `fib(2)`. So `fib(3)` is calculated more than once.
DP avoids this repeated work by storing results.
Optimal Substructure
Optimal substructure means the answer to a bigger problem can be built from answers to smaller problems.
For example, the nth Fibonacci number can be built from the previous two Fibonacci numbers.
```c
fib[n] = fib[n - 1] + fib[n - 2];
```
Two Main DP Approaches
There are two common ways to write DP: memoization and tabulation.
Memoization
Memoization is a top-down approach. We write the solution recursively and store results in an array so repeated calls return quickly.
- Start from the main problem
- Break it into smaller recursive calls
- Store answers when they are calculated
- Reuse stored answers when the same call appears again
Tabulation
Tabulation is a bottom-up approach. We solve the smallest problems first and use them to build bigger answers.
- Start from base cases
- Fill a table step by step
- Avoid recursion
- Usually easier to control memory and loops
Fibonacci Using Tabulation
Fibonacci is the first DP example many students learn because each value depends on earlier values.
```c
#include <stdio.h>
int main(void) {
int n;
printf("Enter n: ");
scanf("%d", &n);
if (n < 0) {
printf("Invalid input\n");
return 0;
}
int fib[50];
fib[0] = 0;
if (n >= 1) {
fib[1] = 1;
}
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
printf("Fibonacci number = %d\n", fib[n]);
printf("Series: ");
for (int i = 0; i <= n; i++) {
printf("%d ", fib[i]);
}
printf("\n");
return 0;
}
```
How to Think About a DP Problem
Do not start by writing code immediately. First, understand the choices and the smaller states.
- Identify what changes in the problem
- Define the state clearly
- Write the relation between states
- Decide the base case
- Choose memoization or tabulation
- Check time and space complexity
State in DP
A state represents one smaller version of the problem.
In Fibonacci, `fib[i]` means the Fibonacci number at position `i`. Here, `i` is the changing value, so it becomes the state.
In grid path problems, the state may be `dp[row][col]`. In knapsack, the state may depend on item index and remaining capacity.
Recurrence Relation
A recurrence relation tells how to calculate the answer for one state using smaller states.
For Fibonacci, the recurrence is:
```c
fib[i] = fib[i - 1] + fib[i - 2];
```
For many DP problems, finding the recurrence is the main thinking part.
Base Case
Base cases are the smallest answers that are already known.
For Fibonacci:
- `fib[0] = 0`
- `fib[1] = 1`
Without correct base cases, DP code gives wrong answers or may access invalid indexes.
DP vs Normal Recursion
Normal recursion may solve the same subproblem many times. DP stores answers so each subproblem is usually solved once.
This is why DP often reduces exponential time solutions to polynomial time solutions.
Common DP Problem Patterns
- Count ways, such as climbing stairs
- Find minimum or maximum cost
- Choose or skip items
- Work on prefixes of strings or arrays
- Move through a grid
- Split a problem into smaller intervals
Time and Space Complexity
For tabulation, time complexity is usually based on how many states are filled. Space complexity is based on how much table memory is used.
In the Fibonacci example, time is O(n) and space is O(n). It can be optimized to O(1) space by storing only the last two values.
Space Optimization
Some DP problems do not need the full table. If the current answer depends only on the previous one or two states, we can store only those values.
For Fibonacci, `fib[i]` depends only on `fib[i - 1]` and `fib[i - 2]`, so the array can be replaced with two variables.
```c
int first = 0;
int second = 1;
for (int i = 2; i <= n; i++) {
int next = first + second;
first = second;
second = next;
}
```
DP Learning Checklist
- What is the state?
- What are the base cases?
- What is the recurrence relation?
- Should we use memoization or tabulation?
- How many states are there?
- Can the space be optimized?
Practice Question
Write a C program that takes `n` and prints the number of ways to climb `n` stairs when you can climb either 1 step or 2 steps at a time.