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
-1
votes
0answers
16 views

Backtracking Longest Increasing Path Matrix [closed]

How do I implement backtracking to get the coordinates (index) of the longest increasing path in a matrix? The following is my code (diagonal movements allowed): ...
2
votes
2answers
61 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
53 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
69 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
67 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
63 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
276 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
42 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
79 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
85 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
189 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
122 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
79 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
622 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
529 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
87 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
167 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
159 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
196 views

LeetCode: Burst Balloons C#

https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1, ...
4
votes
2answers
205 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
119 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
69 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
109 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
97 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
100 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
115 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
161 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
138 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
172 views

Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
0
votes
1answer
228 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
434 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
195 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
1k 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
479 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
173 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
2k 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
300 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
86 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
470 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
156 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
125 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
129 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
154 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
405 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
2 3 4 5