Dynamic Programming

Let’s solve LeetCode problem 124: Binary Tree Maximum Path Sum. The instructions are as follows: A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. ...

Let’s solve LeetCode problem 55: Jump Game. The instructions are as follows: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Constraints: 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 I solved this in two ways: a less efficient approach using dynamic programming, and a very fast greedy method. Let’s dive in! ...

Let’s solve LeetCode problem 122: Best Time to Buy and Sell Stock II. The instructions are as follows: You are given an integer array prices where prices[i] is the price of a given stock on the \(i\)-th day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock. Find and return the maximum profit you can achieve. ...

Today, let’s look at LeetCode problem 790: Domino and Tromino Tiling. The instructions are as follows: You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. Given an integer \(n\), return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7. In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile. ...

Today, let’s look at LeetCode problem 72: Edit distance. The instructions are as follows: Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character Let’s dive in! The Wagner-Fischer algorithm There are several types of edit distance. This LeetCode problem defines it as the Levenshtein distance. The most common algorithm to compute it is the Wagner-Fischer algorithm. ...