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
147 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$ ...
204 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 ...
357 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. <...
3k 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 ...
132 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 ...
2k 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 ...
540 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 ...
5k views

### Finding all the subsets in an array of integers that sum to a given target

Problem Statement: Given an Array if ints, Find out all the subsets in the Array that sum to a given target value. Example: If the input array is: ...
286 views

### Hackerrank - Maximum Disjoint Subtree Product

Problem statement We define an unrooted tree, T, with the following properties: T is a connected graph with nodes ...
101 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: ...
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 ...
143 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 ...
638 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 <...
138 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 ...
425 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 ...
77 views

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\... 0answers 516 views ### Recursive implementation of integer partition without re-arrangement Problem: Integer partition without re-arrangement Input: An arrangement S of nonnegative numbers {s1, . . . , sn} and an integer ... 1answer 53 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 ... 2answers 44 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 ... 2answers 4k views ### Project Euler #15 — count possible lattice paths I'm not a C programmer, just wanted to make a fast solution to the problem. 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 ... 1answer 73 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" ... 1answer 444 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 ... 3answers 1k views ### Tower Hopper problem recursive approach The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from ... 3answers 144 views ### Splitting a rectangular chocolate bar I'm having trouble with my school homework. I have a chocolate bar that consists of either black, white or black&white (mixed) squares. I'm supposed to divide it in two groups, one that has only ... 1answer 991 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'... 2answers 141 views ### Knapsack01 problem, written in c# Is this code written in a decent style? Appreciate some feedback : ) ... 3answers 6k views ### Calculating the sum of array elements to the left and right I am using C++ to code the following logic: An Array is given we have to traverse the array such that sum of array elements to its left must be equal to sum of elements to its right. BTW this is ... 1answer 402 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 ... 0answers 36 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 ... 2answers 2k views ### Dynamic programming solution to “Climbing Stairs” This is the "Climbing Stairs" problem from leetcode.com: You are climbing a stair case. It takes$n$steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many ... 1answer 486 views ### Solving “Quadruple sum” problem using dynamic programming I am trying to learn dynamic programming using hash table. I was given this the "Quadruple sum" problem from firecode.io as a challenge: Given a sorted array of integers and an integer target, find ... 1answer 118 views ### Maximum sub array sum equal to k Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. For example: Input: nums = [1,1,1], k = 2 Output: 2 ... 1answer 596 views ### Compute the number of ways a given amount (cents) can be changed Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented. My code appears to work (although I am curious to ... 1answer 848 views ### Maximum sum of non-consecutive elements of an array You are given a list of houses on a street, with the numeric value representing the amount of money stashed away in each house. Write a method to find the maximum amount of money you can steal. ... 1answer 249 views ### Counting subsets with sum not exceeding some limit I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the ... 0answers 123 views ### Convert top-down subset sum to bottom-up I have written the code for calculating subset-sum and also printing the first encountered non-empty subset from the left that sums up to the given sum. My code in Java is as follows: ... 2answers 2k views ### “What is the fastest solution for finding the maximum sum of a subarray?” Question Given an array, find the longest continuous sub-array which has maximum sum. My Approach First, I solved this problem using dynamic programming which effectively solved the problem in$...
282 views

Ada the Ladybug has several coins in her wallet. She is wondering, how many different values [sum of some subset of coins] is she able to make (in given range). Input The first line contains two ...
154 views

THIS is the link to the problem on SPOJ. I thought it would be better to give the link to the problem instead of me trying to explain as the question is not very clear at first sight. I was able to ...
893 views

### minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
66 views

### dynamic programming solution for a string ending with 0, 1 or 2

A string that contains only 0s, 1s, and 2s is called a ternary string. Find a total ternary ...
2k views

### Implementation of Longest Common Subsequence

So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more ...
530 views

### Count ways to reach the n’th stair

I have solved Leetcode climbing-stairs problem which is stated as: There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a ...
126 views

### x as the sum of unique integers raised to power n

I've done this problem using recursion. But I'm not sure that could this be optimized for bigger values of x using memoization. ...
183 views

### Dynamic Programming with Project Euler problem 67

I am a beginner with python and programming in general. I started teaching myself about 2 months ago. I've been working my way through Project Euler and a few similar sites to build my chops, and ...
308 views

### HackerRank Equal with Scala

For studying Scala, I wrote some code to solve the Equal problem on HackerRank. But I am stuck on test case #15 due to timeout. Christy is interning at HackerRank. One day she has to distribute ...
70 views

### Largest divisible subset optimization

So this is my solution to the following leetcode problem: https://leetcode.com/problems/largest-divisible-subset/description/ How could I optimize this code? I think the run time is \\$\mathcal{O}(n^2)...
3k views

### Finding alternating sequence in a list of numbers

Please be brutal and treat this as me coding this up for an interview. A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between ...