Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [dynamic-programming]

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

228 questions
Filter by
Sorted by
Tagged with
43 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 ...
162 views

### LeetCode: Burst Balloons C#

https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1, ...
81 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 ...
88 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 "...
69 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 ...
62 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 ...
107 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: ...
219 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 ...
61 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 ...
146 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 ...
105 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 ...
129 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 ...
78 views

### Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
78 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 <...
209 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 ...
117 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 + ...
114 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 ...
92 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 ...
465 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 ...
670 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: ...
408 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 ...
66 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. ...
81 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 ...
98 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 ...
98 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 ...
74 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 ...
651 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 ...
294 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 ...
350 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 ...
620 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 ...
231 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-...
333 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 ...
620 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 ...
222 views

### Printing bowTie pattern in efficient and pythonic way

I've posted code/library to GitHub for first time over here. The code is pretty simple. It generates a BowTie pattern of given size and characters. I did attempt to implement DP by calculating only ...
68 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 ...
145 views

### Find the maximum possible summation of differences of consecutive elements

Array A contains the elements, $A_1,A_2, \ldots, A_N$. And array B contains the elements, $B_1,B_2, \ldots, B_N$. There is a relationship between $A_i$ and $B_i$: any element $A_i$ ...
195 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 ...