Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
262
questions
0
votes
1answer
57 views
Find a sum using just two different digits
The problem statement was pretty easy and I was able to run half of the test cases, but some of the test cases in the end gave me the error of memory limit reached. What can I do here to improve the ...
1
vote
0answers
28 views
Divide a set into subset with some constraints
Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here
Problem:
Given a list Lconsisting of not necessarily unique non-...
4
votes
0answers
52 views
C++ - Longest Common Subsequence
Link to the Problem
Here is my code to compute the length of the longest common subsequence of two integer arrays arr[] and brr[]...
3
votes
0answers
88 views
LeetCode: Stone Game C#
https://leetcode.com/problems/stone-game/
Alex and Lee play a game with piles of stones. There are an even
number of piles arranged in a row, and each pile has a positive
integer number of stones ...
0
votes
1answer
95 views
Code A Primitive Calculator ( x3,x2,+1) Using Dynamic programming [closed]
Question -You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given ...
0
votes
1answer
74 views
Generate unique string permutations recursively
🧩 Objective
Write a recursive method for generating all permutations of an input string. Return them as a set.
See: Recursive String Permutations - Interview Cake
🔎 Questions
1: How does the ...
9
votes
1answer
200 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 ...
2
votes
1answer
37 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 ...
3
votes
0answers
69 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 ...
4
votes
1answer
74 views
C++ Dynamic Array Class Testing
I'm creating a basic Dynamic Array class in C++, and I'd like to know if there are any bugs/memory leaks I haven't noticed yet.
dyn_arr.h :
...
2
votes
1answer
53 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:
...
2
votes
2answers
97 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 ...
0
votes
1answer
128 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 ...
1
vote
1answer
69 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 ...
-1
votes
1answer
102 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 ...
2
votes
1answer
95 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, ...
1
vote
1answer
64 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 ...
1
vote
2answers
65 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 ...
2
votes
2answers
63 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 ...
1
vote
1answer
55 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 ...
2
votes
1answer
81 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/...
2
votes
2answers
96 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 ...
2
votes
1answer
67 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 ...
3
votes
2answers
780 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 ...
1
vote
1answer
44 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:
...
3
votes
1answer
96 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.
...
1
vote
2answers
86 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 ...
7
votes
1answer
398 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 ...
2
votes
1answer
191 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 ...
5
votes
1answer
94 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 ...
6
votes
3answers
716 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 ...
7
votes
2answers
540 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
...
1
vote
0answers
50 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 ...
2
votes
2answers
97 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 ...
3
votes
2answers
195 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, ...
0
votes
1answer
284 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 ...
7
votes
2answers
218 views
LeetCode: Burst Balloons C#
https://leetcode.com/problems/burst-balloons/
Given n balloons, indexed from 0 to n-1, ...
4
votes
2answers
223 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 "...
3
votes
2answers
138 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 ...
1
vote
0answers
72 views
Recursion to dynamic programming [closed]
I was trying to solve a problem on de-arrangements (Number of partial derangement such that exactly prime number discs are found away from their natural positions? (Any number of non-prime K disks ...
3
votes
1answer
110 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
...
5
votes
2answers
100 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 ...
0
votes
1answer
72 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 ...
1
vote
1answer
133 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 ...
7
votes
3answers
124 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 ...
2
votes
1answer
46 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 ...
3
votes
2answers
169 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 ...
4
votes
1answer
211 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 ...
2
votes
0answers
212 views
Bursting Balloons
This is a Leetcode problem -
Given n balloons, indexed from 0 to n-1. Each balloon is ...
0
votes
1answer
416 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 <...
