Dynamic_Programming

4 posts with the tag “Dynamic_Programming”

Leetcode 3906: Count Good Integers on a Grid Path

Apr 23, 2026

Intuition

A “Good Integer” is simply an 16 digit integer whom has a non decreasing subsequence of integers at seven certain postions. The good integer itself doesnt have to be sorted, only the digits at those positions. Also the problem asks to find the total number of good integers within a given range.

The problem specifies that the 16 digit integer can be arranged into an imaginary four by four matrix, and that the given directions array controls how this matrix is traversed. This imaginary matrix traversal is what gives the directional path defined subsequence of visitied digits we want to check.

Digit DP, but with some extra logic to check previous digits at certain goal points. The problem boils down to finding out if certain positions depending on the given directions array can form a non decreasing subsequence of 7 digits. Starting from top left / most significant digit, and traversing as needed.

Biggest idea is dont actually try and create a 4 by 4 matrix for each integer possible in between the range, but rather use Digit DP to explore each possibility. Instead of moving down and right in a matrix, instead just jump forward in an array of digits either 1 or 4 depending on the given direction.

Approach

Create an array of digits with the given l and r numbers, whilst including enough leading zeros to to create an digit array of length 16. Then use digit DP to traverse possibiltiies between the given range, whom’s digits at certain positions follow the non decreasing pattern. For state, I use a seperate pos variable for tracking the current digit position, a dir variable for tracking which direction im evaluating, and a goal variable to check wether or not I reached the next position to check the previous digit of the path defined sequence.

Similar to other range summation problems, return both the amount of “Good Integers” possible from 0 to r, then subtract that by the possible count of 0 to l-1. Just like always, to avoid time limit errors, we use the power a memoization hashmap to protect our time.

TLDR

Digit DP to explore valid options recursively for a given range whilst simulating matrix traversal without actually creating a four by four matrix. Subtract the amounts found for left and right to get the total number of good integers.

Leetcode 55: Jump Game

Jul 4, 2025

DevGod

Elf Vtuber

Question

In this Leetcode question, we are given an array of numbers. We start at the first index of the array, and our goal is to reach the end of the array. Each value of the array represents the maximum jump distance to the right. For example, if the first index’s value is 5, you could jump anywhere between 1 to 5 indexs ahead. If the index’s value is 0, then we are NOT allowed to jump anywhere beyond that spot, effectively trapping us. It is important to note that we are never given negative values in the given array. This means that leftward jumps are never allowed, given this constraint of the array Numbers.

Our goal is to determine if we can reach the end using any series of jumps. We return true or false depending on the reachability of the array’s end.

Solving

To solve this Leetcode problem, I used a greedy approach. I used a for loop to iterate left to right through the array. Whilst I traverse the array, the variable named maxJump records the furthest reachable index. In-between iterations, I check whether my current position is ‘impossible’ to reach. If an impossible index is detected, we return false and terminate early. If we go throughout the entire array, from left to right, without hitting an impossible to reach spot, we return true.

TLDR:

Used a Greedy approach to traverse the array, determining if the array’s end is reachable using any series of jumps. I solved this problem by iterating throughout the array, searching for impossible to reach spots.

Leetcode 121: Best Time to Buy and Sell Stock

Jul 3, 2025

DevGod

Elf Vtuber

Question

For this Leetcode problem, we are given an array of numbers representing the fluctuating values of an imaginary stock. Each index of the given array represents a new day. Using this array, we must determine the maximum possible profit that can be achieved. The profit is determined by choosing ONE day to buy the stock, and one future day to sell the stock. In other words, a key constraint of this specific ‘buying stocks’ problem is the fact we are limited to only one sell and one buy operation.

Solving

To solve this problem, we can use Kadane’s algorithm as a template to find the maximum possible profit. This algorithm is used for many problems involving finding the max subarray sum. In our case, we can use it to find the highest profit peak for buying and selling the stock.

We use a for loop to keep track of our stock’s profits for each given day. To keep track of our current possible profit, each iteration we add the difference between the current Ith day’s value minus the previous day’s price. We use a Math.max(0,curProfit) to greedily ensure our current potential profit never dips below zero. Lastly, we use a variable maxProfit to keep track of the largest potential profit we have seen throughout the array.

TLDR:

I used Kadane’s algorithm as a template to create a maxProfit function, for finding the maximum possible profit achieved by buying and selling a stock.

Leetcode 70: Climbing Stairs

May 13, 2025

DevGod

Elf Vtuber

About

This leetcode problem is about a fictional set of stairs, and finding the total amount of ways you could climb to the Nth step. Whilst climbing the stairs, you can choose to climb at most 1 or 2 steps at a time. Additionally, the problems lets us know that stairs 1,2,3 are equal to 1,2,3 ways respectively. I ended up using Top Down Dynamic Programming alongside Recursion plus Memoization for time optimization.

One way to think about this problem, is to imagine what leads up to your target Nth stair. For example, if you wanted to reach the 100th stair, you have to either climb one step from the 99th stair, or climb two steps from the 98th stair. Since the Nth stair is reachable from the previous two stairs, we can calculate the number of ways to reach the Nth stair by adding together the previous two stairs amount of climbing combinations. This forms a pattern similar to a Fibonacci number problems, where we want to find the answer based on the sum of previous answers we’ve found for the problem.

The sub problem of “Climbing Stairs” is that for each Nth stair, we must find the number of ways the previous two stairs had before adding them together. The base cases of this problem is that for any Nth stair less than or equal to three, the number of ways will be the same value as Nth. It is when stair’s N is greater than three that we must use our DP solution to find the total number of ways to climb up to that stair.

Additionally, since N can get large, I use a hash map named MEMO to store past results to reduce unnecessary recursive function calls, optimizing my solution by relying on cached past results for better speed. If my MEMO has a result for a given step I am looking for, then I just use that. However, if MEMO doesn’t contain the number of ways for the Nth stair I am looking for, then I proceed forward with running my recursive solution.

TLDR

Used Dynamic Programming, Recursion and Memoization to find the each Stairs number of ways to climb. Each Nth stair number of total ways relies on the previous two stairs total ways added together. Stairs 1,2,3 have one way, two ways, and three ways to climb to them respectively.