Skip to main content

Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

Filter by
Sorted by
Tagged with
9 votes
1 answer
2k views

LeetCode on Longest Palindromic Substring in Python

This is a programming question from LeetCode: Given a string s, return the longest palindromic substring in s. Example 1: Input: s = "babad" Output: "bab" Note: "aba" is ...
user avatar
2 votes
1 answer
80 views

Why below recursive DP solution is so slow? (Leetcode Q# 123 - Best Time to Buy and Sell Stock III)

This is regarding leetcode Question# 123. I have solved the question (code below) but the solution is showing "Your runtime beats 5.89 % of cpp submissions."? Is there any additional ...
Rajdeep Paul's user avatar
3 votes
0 answers
678 views

Split money into every possible combination of coin denominations

Background and objective of the code Based on this Dev.to challenge, I wrote the Python code below (TIO link also available). The task was to return the least number of coins in a given denomination ...
agtoever's user avatar
  • 478
2 votes
1 answer
95 views

Find sequence to a target number using restricted set of primitive operations

Given an integer 𝑛, compute the minimum number of operations(+1, x2, x3) needed to obtain the number 𝑛 starting from the number 1. I did this using this code: ...
baapcoder_'s user avatar
2 votes
2 answers
215 views

Knapsack performance issue

I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case. Problem statement There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
Youssef13's user avatar
  • 167
0 votes
1 answer
457 views

LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers II

I'm posting my Python code for LeetCode's 1320. If you have time and would like to review, please do so. Problem You have a keyboard layout as shown above in the XY plane, where each English ...
Emma's user avatar
  • 3,527
1 vote
1 answer
151 views

LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers I

I'm posting my C++ code for LeetCode's 1320. If you have time and would like to review, please do so. Thank you! Problem You have a keyboard layout as shown above in the XY plane, where each English ...
Emma's user avatar
  • 3,527
0 votes
1 answer
368 views

LeetCode 375: Guess Number Higher or Lower II

I'm posting my C++ code for LeetCode's Guess Number Higher or Lower II. If you have time and would like to review, please do so. Problem We are playing the Guess Game. The game is as follows: I pick ...
Emma's user avatar
  • 3,527
2 votes
1 answer
738 views

How can I use the State monad effectively in Haskell?

I have written a simple fibonacci function in Haskell that uses the State monad to save solutions to overlapping sub-problems. Now despite the function working I am not really happy with the solution, ...
Orestis's user avatar
  • 495
1 vote
1 answer
820 views

Maximum subset sum with no adjacent elements

Write a function that takes an array of integers (Both Positive and negative) and return the maximum sum of non adjacent elements. Note that even if all values are negative, I don't have an option to ...
Shashi's user avatar
  • 185
1 vote
2 answers
239 views

Recursive brute-force approach to maximum points you can obtain from cards

I came across this question on Leetcode. The question description is as follows: There are several cards arranged in a row, and each card has an associated number of points. The points are given in ...
Jitesh Malipeddi's user avatar
2 votes
2 answers
79 views

(Java) Read .txt and organize activities for hours / minutes

Doubts in logic to generate the output file according to the example I need that even if he reaches the total_min <720 condition he continues to travel the lines. 720 is the total number of minutes ...
Ronison Matos's user avatar
1 vote
1 answer
91 views

Matrix problem, the path that is the flattest

So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being ...
Andrei Saulea's user avatar
2 votes
1 answer
175 views

LeetCode: Trapping Rain Water DP C#

Please review for performance and C# style. I already solved this question in 1 way. LeetCode: trapping rain water C# I tried also the dynamic programming approch https://leetcode.com/problems/...
Gilad's user avatar
  • 5,311
2 votes
2 answers
496 views

C# - Reapply the manipulation of JS Object in .Net Core

IMPORTANT: I made another version with some improvements: Version 2 Since some months ago I disagree with the native/code methods to manipulate dynamic or ...
MiBol's user avatar
  • 237
2 votes
1 answer
82 views

Is there a route to the end of the jump table?

I'm currently learning about Dynamic Programming and solving a "coding question" related to the topic. Given an array of non-negative integers, you are initially positioned at the first ...
Somya Agrawal's user avatar
3 votes
2 answers
2k views

LeetCode: Longest String Chain (Java)

For the question, I had a pretty messy solution so I would like some advice on how to better use Java to make the code a bit cleaner. Also, a semi-hack that I did that I'm not proud of is checking if ...
togepi's user avatar
  • 85
1 vote
1 answer
52 views

Dynamic SQL query for count data

I'm working on an application that counts the number of employees in each department. Here's my code: ...
Adrian's user avatar
  • 13
3 votes
1 answer
339 views

Find the smallest number of perfect squares that sum to a target

Given a positive integer n, find the smallest number of perfect squares (for example, 1, 4, 9, 16, ...) that sum to n. ...
Somya Agrawal's user avatar
1 vote
2 answers
107 views

A function to scan user input as string

I know that multiple functions are already available. However, I thought of writing my own because I wanted to learn the logic (and also because I thought there wasn't enough confusion :P). Please ...
kesarling's user avatar
  • 352
7 votes
1 answer
1k views

Printing the number of ways a message can be decoded

My below solution to the following problem is exceeding the maximum recursion depth. I am looking for any improvements which i can make. Problem Alice and Bob need to send secret messages to each ...
strawhatsai's user avatar
2 votes
1 answer
2k views

Maximum sum combination

I am trying to solve this question: https://www.codechef.com/problems/TADELIVE Andy and Bob are the only two delivery men of Pizza-chef store. Today, the store received N orders. It's known that ...
nz_21's user avatar
  • 1,041
5 votes
1 answer
347 views

Total number of non overlapping subsets

I am trying to solve this question. The essence of the problem is this: Given a list of school classes with start and end times, find the total number of non-overlapping subsets. I've written up a ...
nz_21's user avatar
  • 1,041
6 votes
3 answers
1k views

Minimum path sum in a triangle (Project Euler 18 and 67) with Python

Project Euler 18 Project Euler 67 As problem 67 is harder, I'll go with that one: By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum ...
Sriv's user avatar
  • 2,740
7 votes
2 answers
662 views

find longest common substring in space O(n)

I am working on the class question find the longest common substring from 2 strings but I would like to return the longest common substring instead of just size of longest common substring.like ...
jacobcan118's user avatar
1 vote
0 answers
126 views

How do I optimize memoization in order to find longest palindromic substring?

I want to find the longest palindromic substring using dynamic programming in Python3. The strings can be as large as this string. I have seen other questions on this problem that successfully solve ...
Aviral Srivastava's user avatar
2 votes
2 answers
145 views

Rod Cutting Problem Code

I am learning dynamic programming. I read articles for the rod cutting problem and I applied it in cpp, and I got a doubt, does the below code solves the problem through memoization (say, previously ...
susil95's user avatar
  • 287
3 votes
2 answers
336 views

LeetCode: Shortest Common Supersequence C#

https://leetcode.com/problems/shortest-common-supersequence/ Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, ...
Gilad's user avatar
  • 5,311
0 votes
1 answer
592 views

Solution to knapsack problem exceeds time and RAM limits

My goal is to code the knapsack problem algorithm. The problem is that a knapsack has a given weight limit, W. I have a collection of items which have a given ...
DY92's user avatar
  • 141
7 votes
2 answers
376 views

LeetCode: Burst Balloons C#

https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1, ...
Gilad's user avatar
  • 5,311
4 votes
2 answers
297 views

LeetCode: House Robber III C#

https://leetcode.com/problems/house-robber-iii/ Please review for performance The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "...
Gilad's user avatar
  • 5,311
3 votes
2 answers
631 views

Determine if a string is a sequence of dictionary words

This is Leetcode problem 139: "Wordbreak" Problem: Given a non-empty string s and a dictionary wordDict containing a list ...
neet's user avatar
  • 91
3 votes
1 answer
129 views

Using Dynamic Programming to reduce time complexity

Input A long string of numbers, A list of numbers in string Output Minimum space needed in long string to match maximum numbers from list Example ...
Santosh Prasad's user avatar
5 votes
2 answers
119 views

Calculate the rates at which users get stuck at each stage

I completed an algorithm problem just as a personal study, and I can't help but feel like my solution is a bit needlessly complicated, although I can't figure out a better way to do it. Here's the ...
John Kim's user avatar
  • 151
0 votes
1 answer
85 views

Optimal BST challenge

I was coding the problem here. I think I have solved it, but I ran into time limit exceeded issues. I am new in Competitive Programming, so I was looking for a better, time efficient logic for solving ...
Excelsior's user avatar
  • 123
1 vote
1 answer
277 views

Project Euler # 21 amicable numbers Python

Let \$d(n)\$ be defined as the sum of proper divisors of \$n\$ (numbers less than \$n\$ which divide evenly into \$n\$). If \$d(a) = b\$ and \$d(b) = a\$, where \$a ≠ b\$, then \$a\$ and \$b\$ are an ...
user avatar
6 votes
2 answers
306 views

Project Euler #14: Longest Collatz Sequence starting point

Problem statement: The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Using the rule above and starting with 13, we ...
user avatar
2 votes
1 answer
78 views

Length of the longest common sub sequence bottom up

Could I get some feedback on this code? I included a test case as well. This code computes the longest common sub sequence given paired data, it was not part of any challenge I just did it to learn ...
justanothertechdude's user avatar
3 votes
2 answers
821 views

Optimal burger-eating challenge

Little history to give context to the problem: The Krusty-Burgers Homer Simpson is a smart guy who likes to eat Krusty-Burgers, and it takes m minutes for Homer ...
Gabriel's user avatar
  • 391
4 votes
1 answer
627 views

The Dungeon game

This is a Leetcode problem - The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our ...
Justin's user avatar
  • 2,489
2 votes
0 answers
370 views

Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
Justin's user avatar
  • 2,489
0 votes
1 answer
899 views

Python program to solve the "rod-cutting problem"

An assignment at school required me to write a program for this task: In the rod-cutting problem, we are given a rod of length n inches and a table of prices <...
Justin's user avatar
  • 2,489
3 votes
0 answers
1k views

Python program to solve matrix-chain multiplication

An assignment at school required me to write a Python program for this task: In the matrix-chain multiplication problem, we are given a sequence of matrices ...
Justin's user avatar
  • 2,489
3 votes
0 answers
229 views

Longest Palindrome Substring: Where is the dynamic programming? [closed]

In this LeetCode problem, Longest Palindromic Substring, it is listed under Dynamic Programming for Google interview preparation. My understanding of dynamic programming is roughly "recursion + ...
Scott Skiles's user avatar
3 votes
1 answer
2k views

Python program for "0-1 knapsack problem"

Here is what a knapsack/rucksack problem means (taken from Wikipedia): Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that ...
Justin's user avatar
  • 2,489
5 votes
1 answer
150 views

Identify fraudulent bank transactions

Task: Return true if a transaction is allowed and return false if transaction is prohibited. Details: 1. String is represented as an "array" that can contain up to three elements. We need to ...
user194076's user avatar
0 votes
1 answer
633 views

CodeChef Matches challenge

I am solving some problems from CodeChef but I am stuck on the Matches problem: Ari and Rich are playing a pretty confusing game. Here are the rules of the game: The game is played with ...
ADITYA JOSHI's user avatar
0 votes
2 answers
501 views

Making Anagram Problem Implementation

Problem Statement Alice is taking a cryptography class and finding anagrams to be very useful. We consider two strings to be anagrams of each other if the first string's letters can be rearranged to ...
Anit Shrestha's user avatar
1 vote
0 answers
2k views

Hackerrank Beautiful Strings

Problem Statement You are given a string, S , consisting of lowercase English letters. A string is beautiful with respect S to if it can be derived from S by removing exactly 2 characters. ...
Rajat Saxena's user avatar
2 votes
1 answer
98 views

Finding maximum homework grade ECOO 2018

I'm trying to solve ECOO 2018 round 2(regionals) question 2 to prepare for the upcoming contest. Basically, in the question George has to achieve the maximum possible grade by completing the right ...
Michael exe's user avatar