Longest Arithmetic Subsequence with Difference Constraint
Given a list of integers nums and an integer diff, return the length of the longest arithmetic subsequence where the difference between each consecutive numb...
Posts with tag 'dynamic programming'
Longest Increasing Path
Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right.
Number of Palindromic Substrings
Given a lowercase alphabet string s, return the number of palindromic substrings in s.
Edit Distance
Given two strings a and b, find the minimum edit distance between the two. One edit distance is defined as
Labyrinthian Possibilities
You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner? Mod the result by 1...
Make a Palindrome by Inserting Characters
Given a string s, return the minimum number of characters needed to be inserted so that the string becomes a palindrome.
Count Exact Sum
Given a list of positive integers nums and an integer k, return the number of subsets in the list that sum up to k.
Longest Zero Sublist Sum
Given a list of integers nums, which contains either -1 or 1, return the length of the longest sublist that sums to 0.
Create Palindrome After Deleting at Most K Characters
Given a string s and an integer k return whether you can delete at most k characters such that after the deletion s is a palindrome.
Skip Tasks to Minimize Work
You are given a list of integers nums representing tasks that you must get through in order. Each value represents the amount of time it takes to finish that...
Airplane Seat Shuffling
You are given an integer n representing the number of seats in an airplane. The first person has lost their ticket, so they pick a random seat. Everyone else...
Largest Square Submatrix
Given a two-dimensional integer matrix, return the area of the largest square of 1 s.
Largest Square Matrix with Same Value
Given a two-dimensional list of integers matrix, find the largest k × k submatrix such that all of its elements are the same value, and return the k.
Delete Characters to Equalize Strings
Given two lowercase alphabet strings a and b, consider an operation where we delete any character in either string. Return the minimum number of operations r...
Count Square Submatrices
Given a two-dimensional list of integers matrix containing 1s and 0s, return the total number of square submatrices with all 1 s.
0-1 Knapsack
You are given two lists of integers weights and values which have the same length and an integer capacity. weights[i] and values[i] represent the weight and ...
Split String Into K Palindromes
Given a lowercase alphabet string s and an integer k, you want to divide the string into k disjoint parts such that each part is a palindrome. Return the min...
Shortest Common Supersequence
Given strings a and b, return the length of the shortest string that has both a and b as subsequences.
Poly Knapsack
You are given two lists of integers weights and values which have the same length and an integer capacity. weights[i] and values[i] represent the weight and ...
Minimum Dropping Path Sum
You are given a two-dimensional list of integers matrix. Return the minimum sum you can get by taking a number in each row with the constraint that any row-a...
Minimum Dropping Path Sum With Column Distance Constraint
You are given a two-dimensional list of integers matrix. Return the minimum sum you can get by taking a number in each row with the constraint that any row-a...
Longest Palindromic Subsequence
Given a string s with all lower case characters, find the length of the longest palindromic subsequence in s.
Longest Common Subsequence of Three Strings
Given lowercase alphabet strings a, b, and c, return the length of their longest common subsequence.
Rod Cutting
You are given a list of integers prices where prices[i] represents the price to sell a rod of size i + 1, and an integer n which represents the current size ...
Decode Message
Given the mapping "a" = 1, "b" = 2, … "z" = 26, and an encoded message message (as a string), count the number of ways it can be decoded.
Longest Increasing Subsequence
Given an unsorted list of integers nums, return the longest strictly increasing subsequence of the array.
Longest Common Substring
Given two lowercase alphabet strings s0, and s1, return the length of their longest common substring.
Longest Common Subsequence
Given two strings a and b, return the length of their longest common subsequence.
Largest Sum of Non-Adjacent Numbers
Given a list of integers nums, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.
Increasing Digits
Given an integer n, return the number of positive integers of length n such that the digits are strictly increasing.
Hoppable
Given an integer list nums where each number represents the maximum number of hops you can make, determine whether you can reach to the last index starting a...
First to Count to Target
You are playing a game against a friend where in each round you pick a number from 1 to k to add to a shared running total that initially starts from 0. The ...
Collecting Coins
You are given a two-dimensional integer matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move ...