Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
236
questions
7
votes
1answer
114 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
84 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
62 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
547 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
504 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
44 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
76 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
154 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
94 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
171 views
LeetCode: Burst Balloons C#
https://leetcode.com/problems/burst-balloons/
Given n balloons, indexed from 0 to n-1, ...
4
votes
2answers
184 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
94 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
66 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
97 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
...
4
votes
2answers
95 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
66 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
75 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 ...
6
votes
3answers
109 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
43 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
155 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
121 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
90 views
Bursting Balloons
This is a Leetcode problem -
Given n balloons, indexed from 0 to n-1. Each balloon is ...
0
votes
1answer
143 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 <...
3
votes
0answers
256 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 ...
2
votes
0answers
173 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 + ...
3
votes
1answer
361 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 ...
5
votes
1answer
115 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 ...
0
votes
1answer
469 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 ...
0
votes
2answers
118 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 ...
1
vote
0answers
806 views
HackerRank Equal Solution [closed]
Source: https://www.hackerrank.com/challenges/equal/problem
Problem Description:
Christy is interning at HackerRank. One day she has to distribute some
chocolates to her colleagues. She is ...
1
vote
0answers
121 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.
...
2
votes
1answer
84 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 ...
3
votes
2answers
302 views
Counting the number of ways to decode a string
I am working on problem where I need to decode a string:
A message containing letters from A-Z is being encoded to numbers
using the following mapping:
'A' -> 1
'B' -> 2
...
...
2
votes
1answer
108 views
Given a string and a word dict, find all possible sentences
I have been trying to figure out how to meet space and time complexity requirements for the following leet code question. I have come up with two versions, one that meets the time requirements and ...
8
votes
2answers
118 views
(Codewars Kata) Memoised Log Cutting
(I am not sure of the official CS name for the problem in question, so I just gave it the name of the kata).
Problem
CLEAR CUTTER'S NEEDS YOUR HELP!
The logging company Clear Cutter's ...
3
votes
2answers
111 views
Longest common subsequence solution
I've seen this today on a mock interview and wanted to give it a try. I'd love to hear some feedback from you guys. This is my second attempt at the problem, initially I had a mess of ...
0
votes
0answers
102 views
Recursive Dynamic programming with 3D arrays consuming time
I am trying to solve a question given on Codeforces involving dynamic programming with 3D arrays.
F. Trucks and Cities
There are \$n\$ cities along the road, which can be represented as a ...
3
votes
1answer
89 views
Simple DP problem solved in compile time
The problem is taken from one of recent SO questions:
Finding max sum of matrix elements with following constraints:
Exactly one row element has to be included in the sum
If element at (i, j) is ...
2
votes
1answer
54 views
Number of way to render an amount of money
I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain ...
2
votes
3answers
330 views
Leetcode #91 - Number of ways to decode a string
I'm working on problem 91 on Leetcode.com called Decode Ways and I've successfully managed to get a working recursive solution but it results in Time Limited ...
1
vote
3answers
409 views
Subarray Sum Equals K
I've written a solution to the following leetcode problem:
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example ...
0
votes
1answer
744 views
Javascript Fibonacci with dynamic programming
Trying to applying what seen on What Is Dynamic Programming and How To Use It (here: https://www.youtube.com/watch?v=vYquumk4nWw )
Obviuously this is the final code, after removing the recursion.
I ...
1
vote
1answer
283 views
Odd Even Subarrays
I've been trying to understand Dynamic Programming lately, here's the question I just attempted:
You are given an array A of N positive integer values. A subarray of this array is called an Odd-...
-2
votes
1answer
467 views
Dynamic Programming solution for one pile nim game
I have solved the following problem using dynamic programming: Little Deepu and his Girlfriend 1. To paraphrase,
We have two players Little Deepu and Kate and M items in the bag B,
also we have ...
1
vote
0answers
69 views
selecting 5 best players out of 2 team
Let us assume that we need to develop an application which can select best 11 players to score maximum points. The application will select the best players after completion of a match. The rules are ...
4
votes
3answers
825 views
Find smallest number of squares that sum to a number
Leetcode problem 279 “Perfect Squares” is:
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...)
I wrote the following solution:
...
3
votes
1answer
225 views
Minimum steps to 1 to find minimum operations to transform n to 1
I was doing this JavaScript problem called "Minimum steps to 1." You can find the problem here.
Given a positive integer - num, Following is a list of possible operations which can be performed on ...
2
votes
1answer
393 views
Coin sum dynamic programming in Python
I am preparing for an interview, and here's a popular problem on the dynamic programming. And I want to see if there's any feedback or code review for my solution at dynamic programming question.
<...
3
votes
1answer
3k views
Solving maze problem with backtracking solution using stack
I solved the maze backtracking question using a stack however could not find any other solution like that anywhere (to validate my solution is actually a valid one).
The problem statement is as ...
3
votes
1answer
144 views
Demonstration of the Largest Square Submatrix
Challenge
Using the C++ language, have the function MaximalSquare(strArr) take the strArr parameter being passed which will ...
