We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

232 questions
Filter by
Sorted by
Tagged with
412 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 ...
475 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 ...
65 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 ...
95 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 ...
41 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 ...
155 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 "...
142 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, ...
71 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 ...
168 views

### LeetCode: Burst Balloons C#

https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1, ...
80 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 ...
65 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 ...
108 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 ...
94 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 ...
192 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: ...
248 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 ... ...
65 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 ...
65 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 ...
2k 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 ...
39 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 ...
148 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 ...
110 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 ...
169 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 ...
82 views

### Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
94 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 <...
257 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 ...
140 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 + ...
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 ...
97 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 ...
467 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 ...
736 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: ...
534 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 ...
76 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. ...
82 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 ...
87 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 ...
116 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 ...
100 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 ...
106 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 ...
80 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 ...
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 ...
653 views

### Multiple 0-1 knapsack

I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs. Input description The first input line consists of two positive integers N e ...
1k views

### Student Attendance Record II

I'm currently working on the Student Attendance Record II problem: Given a positive integer $n$, return the number of all possible attendance records with length $n$, which will be regarded ...
305 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 ...
4k views

### Longest Increasing Subsequence

I am learning dynamic programming and I have written down some code for longest increasing subsequence. I would like to know if there is any case or any area of improvement in the terms of ...
62k views

### Dynamic programming knapsack solution

I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
371 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 ...
660 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 ...
248 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-...
408 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 ...