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
-4
votes
0answers
20 views

How to find max possible wins for 2 player with numbered cards? [closed]

I have the following situation: There are 2 Player Each player has 'X' cards To find: max number of wins of Player 1 possible ...
2
votes
1answer
66 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
58 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
60 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 index of ...
3
votes
2answers
173 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
41 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
78 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
84 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
139 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
114 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
68 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
603 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
519 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
47 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
81 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
164 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
128 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
192 views

LeetCode: Burst Balloons C#

https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1, ...
4
votes
2answers
195 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
108 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
68 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
107 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
69 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
90 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
114 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
44 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
159 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
128 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
148 views

Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
0
votes
1answer
191 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
330 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 ...
3
votes
0answers
189 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
794 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
474 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
155 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
1k 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
199 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
85 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
408 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
137 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
121 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
122 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
124 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
373 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
444 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
824 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
2 3 4 5