Dynamic Programming Made Easier.

This post talks about certain dynamic programming strategies and how to make it easier

Dynamic Programming : In my view one of the toughest topics that I have had to prepare for programming. And honestly, till this date , I don’t really think I have had a complete grasp for it. And when I came across a couple of posts that asked about how to improve with dynamic programming, I knew this wasn’t just a ME problem. I had to do better. So, as usual, I started researching and here’s what I found :

Now before we jump into the problems and patterns, here what I recommend to study :

STUDY METHOD :

These are 6 patterns.

1. Take 1 each day and try to solve problem by yourself in 10 mins.

2. If you cannot, read and understand the solution. But do not solve.

3. Next day, try to solve the problem thinking thru the logic. This way, by 7 days, you should wrap up the preparation.

4. And then in restart. After 4 weeks, these problems should be muscle memory.

5. Then take on newer problems and apply the solution. But most importantly, don’t be disheartened if unable to solve. Its okay. Dynamic programming is tough. Look up the solution and again, try to solve them next day and repeat weekly.

There are broadly 6 groups :

1. Climbing Stairs

2. Grids

3. Two sequences

4. Interval

5. Longest increasing subsequence

6. Knapsack

Now, what are they and what problems to solve for them is listed below :

CLIMBING STAIRS :

Generally (but not limited to) if the problem statement asks for the following:

• Count the total number of ways

• Given multiple ways of doing a task, which way will give the minimum or the maximum output.

We can try to apply recursion. And once we get recursion, we can go ahead and convert it to dynamic programming.

• Try to represent the problem in terms of indexes.

• Try all possible choices/ways at every index according to the problem statement.

• If the question states

  • Count all the ways - return sum of all choices/ways.

  • Find maximum/minimum- return the choice/way with maximum/minimum output.

Problems to Solve :

https://leetcode.com/problems/climbing-stairs/

https://leetcode.com/problems/min-cost-climbing-stairs/

htps://leetcode.com/problems/house-robber/

https://leetcode.com/problems/minimum-cost-for-tickets/

GRIDS :

Given two values M and N, which represent a matrix[M][N]. We need to find the total unique paths from the top-left cell (matrix[0][0]) to the rightmost cell (matrix[M-1][N-1]).

At any cell we are allowed to move in only two directions:- bottom and right.

There are three ways to approach this problem :

1. Memoization Approach

2. Tabulation Approach

The biggest giveaway for these types of problems is the presence of matrix grids.

Imagine you're standing in the top-left corner of an M x N grid.

• Your goal is to get to the bottom-right corner.

• But there’s a catch — you can only move right or down at any point.

So at every step, you have just two options:

• Move right

• Move down

Now, lets think recursively :

At any cell (i, j):

• To reach the destination, you either:

  • Move right to (i, j + 1)

  • Move down to (i + 1, j)

So the number of ways to reach the end from (i, j) is:

paths(i, j)=paths(i+1, j)+paths(i, j+1)

Just like Climbing Stairs where:

ways(n)=ways(n-1)+ways(n-2)

Memoization Approach :

• Base case 1: If you're out of bounds (i ≥ M or j ≥ N), return 0.

• Base case 2: If you're at the bottom-right cell, return 1.

• If we've already computed dp[i][j], return it.

• Otherwise, store and return:

  dp[i][j]= ways from below + ways from rightdp[i][j]

Tabulation Approach :

Grid Filling Idea:

• Start with a dp table filled with 0s

• Set dp[0][0] = 1 → there’s 1 way to be at the start

• For each cell (i, j), we say:

  dp[i][j]=dp[ i−1 ][ j ]+ dp[ i ][ j−1 ]

In the end, dp[M-1][N-1] has the total number of unique paths.

Problems to solve :

• https://leetcode.com/problems/unique-paths/

• https://leetcode.com/problems/unique-paths-ii/

• https://leetcode.com/problems/minimum-path-sum/

Two Sequences :

Dp[i][j] is some value related to the problem solved on prefix of sequence 1 with length i, and prefix on sequence 2 with length j.

DP[i][j]=solution using the first i characters of sequence 1, and first j characters of sequence 2

To compare or align them, we often want to build up solutions step by step by comparing prefixes.

At every step (i, j):

• We're asking: What’s the best solution if we only look at the first i letters of S1 and first j letters of S2?

• The final answer is usually in dp[len(S1)][len(S2)].

Key Idea :

At each cell (i, j), the value usually depends on:

• dp[i-1][j] → ignoring one from S1

• dp[i][j-1] → ignoring one from S2

• dp[i-1][j-1] → matching or editing both

Problems to Solve :

• https://leetcode.com/problems/longest-common-subsequence/

• https://leetcode.com/problems/uncrossed-lines/ (longest common subsequence)

• https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

• https://leetcode.com/problems/edit-distance/

• https://leetcode.com/problems/distinct-subsequences/

• https://leetcode.com/problems/shortest-common-supersequence/

Interval:

DP problem is solved on every single interval (subarray) of the array

Interval DP is used when the problem asks you to consider subarrays (or subranges) of a sequence and make decisions based on those intervals.

In other words:

DP[i][j]=best result for the subarray from index i to j\text{DP}[i][j] = \text{best result for the subarray from index } i \text{ to } jDP[i][j]=best result for the subarray from index i to j

You're trying to compute a result (like cost, max value, or score) for every possible interval [i...j].

You’ll often see Interval DP in problems where:

• You can remove elements from a range

• You need to combine segments or divide the problem

• The order of solving subintervals affects the final answer

For any interval [i, j], you usually try all possible partition points k between i and j:

dp[i][j]=min⁡/max⁡(dp[ i ] [ k ]+dp [ k+1 ][ j ] + cost(i, k ,j))

You're essentially:

• Splitting the interval

• Solving both halves recursively

• Combining their results with some additional cost or rule

Problems to solve :

• https://leetcode.com/problems/longest-palindromic-subsequence/

• https://leetcode.com/problems/stone-game-vii/

• https://leetcode.com/problems/palindromic-substrings/

• https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/

• https://leetcode.com/problems/burst-balloons/ (very hard, can be avoided)

Longest increasing subsequence

Dp problem is solved on every prefix of the array. Transition is from every index j < i.

At index i, you look back at all previous indices j (0 ≤ j < i) and ask:

"Can I extend the increasing subsequence that ends at j by including nums[i]?"

If nums[j] < nums[i], then:

dp[i]= max⁡( dp [ i ], dp [ j ] + 1 )

So you're saying:

• “If nums[i] is greater than nums[j], I can build on the LIS that ends at j”

• You update dp[i] with the best such possibility

Problems to solve :

• https://leetcode.com/problems/count-number-of-teams/

• https://leetcode.com/problems/longest-increasing-subsequence/

• https://leetcode.com/problems/partition-array-for-maximum-sum/

Knapsack

Dp state is similar to the classical knapsack problem.

You are given:

• A list of n items

• Each item has a weight and a value

• A capacity W (maximum weight the knapsack can hold)

Goal:
Maximize total value without exceeding the weight capacity

For each item i and weight w, you have two choices:

1. Don’t take the item

   dp[i][w]= dp [ i−1 ][ w ]

2. Take the item (if it fits)

   dp [i][w]=max⁡( dp [ i ][ w ], dp [i−1] [ w− weight[ i] ] + value[i] )

You choose the better of the two.

Problems to solve :

• https://leetcode.com/problems/partition-equal-subset-sum/

• https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

• https://leetcode.com/problems/combination-sum-iv/

• https://leetcode.com/problems/ones-and-zeroes/

• https://leetcode.com/problems/coin-change/

• https://leetcode.com/problems/coin-change-ii/

• https://leetcode.com/problems/target-sum/

• https://leetcode.com/problems/last-stone-weight-ii/

• https://leetcode.com/problems/profitable-schemes/

Hope you find this helpful. Obviously, without a doubt, do solve blind 75 and if you need more solve neetcode 150 DP problems