Dynamic Programming

Brief Introduction

Dynamic Programming (DP) is a problem-solving technique used to solve complex problems by breaking them down into simpler subproblems. It is particularly useful for optimization problems, where you need to find the best solution among many possibilities.

The key idea behind DP is that instead of solving the same subproblem multiple times, you solve it once and store the result (usually in a table or array) for future reference. This technique avoids redundant calculations and improves efficiency, making it much faster than naive recursion.

DP is typically used in problems with overlapping subproblems and optimal substructure, meaning the solution to the overall problem can be constructed from solutions to subproblems. Common applications include finding the shortest path, knapsack problems, longest common subsequences, and various combinatorial problems.

There are two main approaches to DP:

Top-down (Memoization): This involves solving the problem recursively and storing results of subproblems in a cache (usually an array or hash table).
Bottom-up (Tabulation): This involves solving all subproblems starting from the smallest one and building up to the solution of the overall problem.

Generated by ChatGPT

DP is the most important algorithm to learn now.

Codeforces DP Tutorial and Problem Listhttps://codeforces.com/blog/entry/67679

Classic Problems

Kadane’s Algorithm (Maximum / Minimum Contiguous Subarray Sum)

Given an array $a$ with $n$ elements. What’s the maximum / minimum contiguous subarray sum?

This is a very classic DP problem, with its core idea is continuously updating the current subarray sum while traversing the array and records the global maximum.

Let’s talk about the maximum first.

Define the state $dp[i]$ represents the maximum sum of a contiguous subarray ending at the $i^{th}$ element. And the goal is to find the maximum value among all $dp[i]$.

For the $i^{th}$ element, there are two choices:

Add it to the previous contiguous subarray
Start a new contiguous subarray

Thus, the state transition equation is: $$dp[i] = max(dp[i-1] + a[i], a[i])$$

What’s more, since the array of $dp$ is linear and we won’t use it later, we can just use a variable $current_sum$ to record. So the code will be easy to write:

int max_sum = -INF, current_sum = 0;

for(int x = 1; x <= n; x++)
{
    current_sum = max(current_sum + a[x], a[x]);
    max_sum = max(max_sum, current_sum); // Update answer
}

cout << max_sum << endl;

What about the minimum? It’s simple too, with transition equation: $$dp[i] = min(dp[i-1] + a[i], a[i])$$

The most important is, the time complexity is $O(N)$.

Stairs Problem

You are climbing a staircase. It takes $N$ steps to reach to the top. Each time you can either climb 1 or 2 steps. And you can make most $K$ jumps. In how many distinct ways can you climb to the top?

We have $N$ steps to take, and each step can be $k$(from $0$ to $K$) jumps. So we need to have a 2-dimensional dp array, let’s say $dp[i][k]$, with $i$ from $0$ to $N$, $k$ from $0$ to $K$.

Moreover, the transition equation will be $$dp[i][k] = dp[i-1][k-1] + dp[i-2][k-1]$$for sure. And the answer will be $dp[N][K]$.

Minimum Path Sum

Given a grid of $n$ x $m$, find a path from the top-left to the bottom-right corner that minimizes the sum of numbers along the path. You can only move right or down. And you can’t make two consecutive steps down.

For the grid walking we need a 2-dimensional array $s[i][j]$, but “can’t make two consecutive steps down” is also a state to consider. Thus, the array can be $dp[i][j][2]$, where $dp[i][j][0]$ refers to $s[i][j]$ and the previous step is “walking right”, similarily, $dp[i][j][1]$’s previous step is “walking down”.

Therefore, the transition equation will be$$dp[i][j][0] = min(dp[i][j-1][0], dp[i][j-1][1]) + grid[i][j]$$and$$dp[i][j][1] = dp[i-1][j][0] + grid[i][j]$$(because we can’t make two consecutive steps down). And the answer will be $min(dp[n][m][0], dp[n][m][1])$.

In dynamic programming problems, you must think what is important so far after we made some decisions, after we already chose some numbers, or in graghs after we got to this vertex.

Line of wines

There are $N$ wines in a row. Each year you sell either the leftmost or the rightmost wine. The $i^{th}$ wine has initial price $p[i]$ and price $k*p[i]$ in the $k^{th}$ year. What is the maximum possible total profit?

Since the choose order will affect the profit, and each choose can’t be easily conclued by sorting, greedy is useless here and it won’t lead to an optimal solution.

Considering the middle status, e.g. We have sold the $1^{st}$ and the $N^{th}$ wines after 2 years, remaining the $2^{nd}$ to the $(N-1)^{th}$ wines. So we have two variables $L$(remaining left), $R$(remaining right), and years past $Y$ will be easily calculated. We set the array as $dp[L][R]$.

So the transition equation will be $$dp[L][R] = max(Y·p[R]+dp[L+1][R], Y·p[R]+dp[L][R-1])$$ One tricky thing here is to figure out in what order we should go through the states.

The dp array should be initialized like $dp[i][i] = p[i]*N$, which is the last wine’s score. And the answer will be $dp[1][N]$.

for(int x = 1; x <= N; x++) dp[x][x] = p[i] * N;

for(int L = N; L >= 1; L--)
{
    for(int R = L; R <= N; R++) // This is a valid order
    {
        int Y = N-(R-L+1);
        dp[L][R] = max(Y*p[R]+dp[L+1][R], Y*p[R]+dp[L][R-1]);
    }
}

cout << dp[1][N] << endl; // Answer