Dynamic Programming

Competitive Programming/Dynamic Programming.md

Dynamic programming is an algorithm design technique that can be used to find optimal solutions to problems and to count the number of solutions.

Problem: Suppose we are given a set of coins coins = {c_1, c_2, c_3} and a target sum of money $n$ , and we are asked to construct the sum $n$ using as few coins as possible. In other words, we have to minimize the number of coins $c_i$ such that $\sum c_i=n$ .

Greedy algorithms in these types of problem generally do not work.
Brute force algorithms might work, but it would be very slow for large inputs.
Hence, we resort to the use of dynamic programming, it is similar to a brute force but is efficient.

Let coins = {1, 3, 4} and let solve(x) be the minimum number of coins required to forma sum of $x$ . To solve the problem, the idea is to focus on the first coin that can be 1, 3, or 4. If we choose coin 1, the remaining task is to form the sum $n-1$ using the minimum number of coins. This is recursion!

solve(x) = min(solve(x-1)+1, solve(x-3)+1, solve(x-4)+1)

Explicitly, we can write it as:

\text{solve}(x) = \begin{cases} \infty & \text{if } x < 0 \\ 0 & \text{if } x = 0 \\ \min_{c \in \text{coins}} \left( \text{solve}(x - c) + 1 \right) & \text{if } x > 0 \end{cases}

In C++, we can write the code as

int solve(int x) {
	if (x < 0) return INF;
	if (x == 0) return 0;
	int best = INF;
	for (auto c : coins) {
		best = min(best, solve(x-c)+1);
	}
	return best;
}

NOTE: The code above is still not efficient since there may be a large number of ways to construct the sum and the function checks all of them.

Memoization

The key idea in dynamic programming is memoization, which means that we store each function value in an array directly after calculating it. Then, when the value is needed again, it can be retrieved from the array without recursive calls.

To solve the problem, we create arrays:

bool ready[N];
int value[N];

where ready[x] indicates whether the value of solve(x) has been calculated, and if it is, value[x] contains this value. The constant $N$ has been chosen so that all required values fit in the arrays.

After this, the function can be efficiently implemented as follows:

int solve(int x) {
    if (x < 0) return INF;
    if (x == 0) return 0;
    if (ready[x]) return value[x];
    int best = INF;
    for (auto c : coins) {
        best = min(best, solve(x - c) + 1);
    }
    ready[x] = true;
    value[x] = best;
    return best;
}```

The time complexity of the algorithm is $O(nk)$ where $n$ is the target sum and $k$ is the number of coins.

## Iterative Implementation
We can use iterative algorithm to construct the solution. 
```cpp
value[0] = 0;
for (int x = 1; x <= n; x++) {
	value[x] = INF;
	for (auto c : coins) {
		if (x-c >= 0) {
			value[x] = min(value[x], value[x-c]+1);
		}
	}
}

Constructing a Solution

If asked to find the value of an optimal solution and to give an example how such a solution can be constructed, we can declare a new array that indicates for each sum of money the first coin in an optimal solution.

int first[N];
value[0] = 0;
for (int x = 1; x <= n; x++) {
	value[x] = INF;
	for (auto c : coins) {
		if (x-c >= 0 && value[x-c]+1 < value[x]) {
			value[x] = value[x-c]+1;
			first[x] = c;
		}
	}
}

while (n > 0) {
	cout << first[n] << "\n";
	n -= first[n];
}

Counting Solutions

If asked for the total number of solutions, we can just simply count the solutions. The general recursive function is given as follows:

\text{solve}(x) = \begin{cases} 0 & \text{if } x < 0 \\ 1 & \text{if } x = 0 \\ \sum_{c \in \text{coins}} \text{solve}(x - c) & \text{if } x > 0 \end{cases}

The following code below constructs an array count such that count[x] equals the value of solve(x) for $0 \leq x \leq n$ .

count[0] = 1;
	for (int x = 1; x <= n; x++) {
		for (auto c : coins) {
			if (x-c >= 0) {
				count[x] += count[x-c];
		}
	}
}

Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem aims to find a subsequence within an array that is as long as possible, where each element is strictly greater than the preceding one.

Dynamic Programming Approach

Define a function: Let $length(k)$ be the length of the longest increasing subsequence that ends at index $k$ .
Recurrence Relation: To compute $length(k)$ , we look at all previous indices $i < k$ . If $array[i] < array[k]$ , it means we can extend an increasing subsequence ending at $i$ with the element at $k$ . Therefore, the value of $length(k)$ is calculated as: $length(k) = 1 + \max(\{length(i) \mid 0 \le i < k \text{ and } array[i] < array[k]\})$ If no such index $i$ exists, $length(k) = 1$ (the subsequence is just the element itself).
Final Result: The length of the overall LIS for the entire array is the maximum value found in the length array after computing it for all indices from $0$ to $n-1$ .

This logic is typically implemented with a length array and nested loops.

// n is the number of elements in array
int length[n];

for (int k = 0; k < n; k++) {
  length[k] = 1;
  for (int i = 0; i < k; i++) {
    if (array[i] < array[k]) {
      length[k] = max(length[k], length[i] + 1);
    }
  }
}

Paths in a Grid

This problem involves finding a path in an $n \times n$ grid from the top-left corner to the bottom-right corner. The only allowed moves are down and right. The goal is to find the path that maximizes the sum of the values in the cells visited.

Dynamic Programming Approach

Define a function: Let $sum(y, x)$ be the maximum possible path sum from the top-left corner to the cell at coordinates $(y, x)$ .
Recurrence Relation: To reach cell $(y, x)$ , you must have come from either the cell above, $(y-1, x)$ , or the cell to the left, $(y, x-1)$ . To maximize the sum, we choose the path with the larger preceding sum. The formula is: $sum(y, x) = \max(sum(y-1, x), sum(y, x-1)) + \text{value}[y][x]$ The base cases are the cells on the top and left edges of the grid.
Final Result: The maximum sum for any path through the entire grid is the value calculated for the bottom-right corner, $sum(n, n)$ .

Algorithm Implementation

A 2D array, sum[N][N], stores the maximum path sums for each cell. The values are calculated using nested loops that iterate through the grid.

int sum[N][N];

// Assuming 1-based indexing for an n x n grid
for (int y = 1; y <= n; y++) {
  for (int x = 1; x <= n; x++) {
    sum[y][x] = max(sum[y][x-1], sum[y-1][x]) + value[y][x];
  }
}