Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
4
votes
1answer
77 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
57 views
Bursting Balloons
This is a Leetcode problem -
Given n balloons, indexed from 0 to n-1. Each balloon is ...
0
votes
1answer
43 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
75 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
47 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 + ...
2
votes
1answer
125 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
88 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
438 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
73 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
102 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
36 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
79 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 ...
0
votes
1answer
135 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
89 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
110 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
83 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
63 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
81 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
52 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
259 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
265 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
433 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
154 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
244 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
63 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
458 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
109 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
251 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
2k 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
99 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 ...
8
votes
4answers
1k views
Project Euler #15: counting paths through a 20 × 20 grid
I've recently solved Project Euler's 15th problem stating:
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom ...
3
votes
2answers
364 views
Memoized solution to Count number of ways to climb n steps
Problem statement : A Child is climbing up n steps with either 1 , 2, 3 hops ..how many ways can the child climb up the stairs?
source: cracking the coding interview book.
I have two solutions the ...
3
votes
1answer
100 views
5 CPU's Task scheduling N process
Question.
There are 5 CPUs and N number of tasks in the queue. You have to use
minimum CPUs to process the tasks.
A task is of format [arrival time, time to process the task].
Note:
...
6
votes
3answers
2k views
Performance of dynamic Fibonacci generator and dead rabbits
I would like to improve my code style and its efficiency.
I'm just moving beyond the standard recursive approach to a lot of simple algorithms.
This post has two code snippets with slightly ...
3
votes
1answer
464 views
Solving the Burst Balloon problem using Dynamic Programming
Continuing where I left off previously to solve the problem described here, I've now solved the same using dynamic programming (following Tikhon Jelvis blog on DP).
To refresh, the challenge is to ...
2
votes
0answers
113 views
Smith-Waterman algorithm for local sequence alignment with affine gap penalties
The following is a summary from the top of my head so please correct me if I'm wrong. See the Wikipedia article for more.
This is about determining the (score / edit distance of the) most similar ...
2
votes
0answers
414 views
Robot on a Grid: Find a path between two corners with forbidden cells on the road
Problem statement
The problem is defined in the book as following:
8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
0
votes
2answers
348 views
Number of Paths (BackTracking) in Java
Illustration
You're testing a new driverless car that is located at the Southwest
(bottom-left) corner of an n×n grid. The car is supposed to get to the
opposite, Northeast (top-right), corner ...
2
votes
1answer
49 views
Dynamic programming to solve two printers with different speeds
I solved this problem using a Class, but thought I might try to figure out this memoization thing.
Problem
There are two printers that print pages at different speeds (X, Y).
What is the ...
3
votes
2answers
43 views
Splitting uppercase letters based on a dictionary
A few days ago I learned about the dynamic programming approach to problem-solving; the thing is, I'm still not sure I am fully grasping the concept.
I decided to write an algorithm that takes a ...
7
votes
0answers
1k views
Minimum cost path of matrix using Python
I was reading this article about finding the minimum cost path from (0,0) to any (m,n) point in a matrix. Using python the ...
4
votes
2answers
73 views
Finding sum of sub vector satisfying inequality
I am asked to implement code that checks if there is a sub vector that has a sum, v_l, that would satisfy \$ \frac{1}{4}mn + 1 \leq v_l \leq v - \frac{1}{4} m n - 1\...
3
votes
1answer
72 views
Dynamic DOM Text Editor Performance
I am creating a text editor that will need to work in the browser, syntax highlight, and allow users to edit files up to 50MB in size (i.e. the space allowed by indexedDB) without an "out of memory" ...
3
votes
3answers
135 views
SPOJ Emoticon challenge
I tried this spoj problem and solved it using Dynamic Programming, but I was getting Time Limit Exceeded. The challenge is to count the number of occurrences of the subsequence "KEK" in each input ...
4
votes
1answer
388 views
Longest Arithmetic Progression Algorithm
Problem Statement:
>
Given a sorted array, find the length of the longest arithmetic progression in it.
Examples:
numbers = new int[]{1, 3, 4, 5, 7, 8, 9}
The length is 5, and the ...
2
votes
1answer
191 views
Check the equality for each subset of a string S against the target T and return a count
I wrote the following code to solve this leetcode problem:
...
1
vote
1answer
735 views
Project Euler Problem 31 (Coin Sum)
I just finished Project Euler 31: Coin sums, which asks how many ways there are to make £2 using British coins (1p, 2p, 5p, 10p, 20p, 50p, £1, and £2).
When I compared my code and the problem review'...
3
votes
2answers
139 views
Knapsack01 problem, written in c#
Is this code written in a decent style? Appreciate some feedback : )
...
2
votes
0answers
34 views
Optimizations for Knapsack with 3 dimensions
Problem Statement:
I am given a set of prices for \$n\$ items I have to find out what is the maximum value I can get with \$M\$ money by selecting exactly \$C\$ items without exceeding the amount of ...
2
votes
1answer
244 views
SPOJ - Alphacode, using dynamic programming
I am currently trying out a programming problem, SPOJ Alphacode, that involves dynamic programming. In an encoding system where A=1, B=2, …, Z=26, a message 25114 ...
