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.

Filter by
Sorted by
Tagged with
50
votes
2answers
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 ...
14
votes
5answers
2k views

DP example for “Power of Two” in Python

I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming. The snippet should show the bottom-up approach of DP. The function ...
12
votes
5answers
7k views

Dynamic programming with Fibonacci

I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code. ...
12
votes
2answers
602 views

Dynamic Programming: Fibonacci-like recurrence relation

This is a problem from my Introduction to Algorithms textbook. Consider the infinite sequence of numbers An|n>0 = (1,1,3,4,8,11,...) defined recursively as follows. $$ A_n = \left\{\begin{aligned} &...
12
votes
1answer
332 views

Counting paths in an n-dimensional grid that stay within the boundaries

Problem Statement You are situated in an N dimensional grid at position (x1, x2, …, xN). The dimensions of the grid are (D1, D2, …, DN). In one step, you can walk one step ahead or behind in ...
11
votes
3answers
2k views

Coin Change: Minimum number of coins

Problem: You are given n types of coin denominations of values \$v(1) < v(2) < ... < v(n)\$ (all integers). Assume \$v(1) = 1\$, so you can always make change for any amount of money \$C\$....
11
votes
3answers
1k views

Optimizing “Herd Sums” problem using dynamic programming

I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think. Herd Sums Execution Time Limit: 2 seconds ...
11
votes
3answers
2k views

Substitution cipher algorithm performance boost

This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 ...
11
votes
1answer
1k views

House-coloring optimization challenge

I have an interview coming up in the next few weeks, and I'm choosing to be interviewed in Python. I began programming in Python (it was about four years ago), so the syntax is natural to me, but I ...
11
votes
1answer
138 views

Loading Data Warehouse with Dynamic SQL

For a data warehousing project I ran into the following: Custom fields that users can create, modify and delete, that should be loaded into the data warehouse as they are when the ETL happens. On ...
10
votes
3answers
3k views

Find the Nth number divisible by only 2,3,5, or 7

I recently participated in a small friendly competition and this was one of the questions: A number whose only prime factors are 2, 3, 5 or 7 is called a humble number. The first 20 humble ...
10
votes
2answers
265 views

Undo format when format disappears

I was posed a question as follows: Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
10
votes
1answer
3k views

Project Euler #14 — longest Collatz sequence

I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's ...
9
votes
2answers
500 views

Justify text from a file using a LaTeX method

I wrote a bit of code that takes a file, justifies the text and writes to another file. It uses a DP approach to minimise a badness metric, which is the amount of undershoot of the line length, cubed ...
8
votes
4answers
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 ...
8
votes
2answers
1k views

Counting Increasing Subsequences of size K recursive

The original description of the problem can be found here, its input here and its expected output here. The problem: Given a integer sequence a1 ... an (-10000 \$\leq\$ ai \$\leq\$ 10000). Where ...
8
votes
3answers
454 views

Handling shared state among a lot of elements in Angular

I am working on a project in Angular where I have a number of similar data objects. When you click on anyone of them it's state and amount of data shown will change. All of the objects start in the ...
8
votes
2answers
211 views

Minimum number of coins problem using dynamic programming - follow up

I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping ...
8
votes
2answers
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 ...
8
votes
2answers
630 views

Quick Sum TopCoder (Brute Force solution)

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the ...
8
votes
1answer
1k views

Assembly line scheduling

This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink. Note: I do understand ...
7
votes
6answers
2k views

Yet another Fibonacci number generator

First attempt at dynamic programming. I want to make this run faster and better. fibonacci.cpp ...
7
votes
4answers
7k views

Python implementation of the longest increasing subsequence

Prompted by this question on Stack Overflow, I wrote an implementation in Python of the longest increasing subsequence problem. In a nutshell, the problem is: given a sequence of numbers, remove the ...
7
votes
2answers
512 views

Recursive function and memorization to find minimum operations to transform n to 1

I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution. ...
7
votes
2answers
168 views

LeetCode: Burst Balloons C#

https://leetcode.com/problems/burst-balloons/ Given n balloons, indexed from 0 to n-1, ...
7
votes
2answers
2k views

Obtaining a target number only using the operations ×2, ×3, and +1

Problem Introduction You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x. Your goal ...
7
votes
4answers
992 views

Repeatedly partitioning an array equally as far as possible

I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases. Nikita just came up with a new array game. The rules are as follows: Initially, ...
7
votes
2answers
474 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 ...
7
votes
1answer
519 views

Three-machine proportionate flow shop problem with unequal machine

As part of an academic project I wrote a code about dynamic programming that solves the "Three-machine proportionate flow shop problem with unequal machine". In flow shop scheduling it is usually ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
160 views

Reading, processing and counting an array setting limits

Last weekend my teacher asked me to create code to solve a problem: Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. ...
7
votes
1answer
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 ...
7
votes
3answers
145 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 ...
6
votes
3answers
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 ...
6
votes
3answers
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 ...
6
votes
2answers
1k views

Box-stacking problem in C++

I have tried to write code of Box stacking problem (mentioned here) in C++ . Kindly give me some views on what mistakes I might have made and how I can improve. It is running for the two inputs I have ...
6
votes
2answers
536 views

UVA 100: “The 3n + 1 problem”

I’ve solved UVA Problem 100: The 3n + 1 problem . In short, the task was to write a program that calculates a maximum of Collatz sequence lengths for any given range of starting values. My program: <...
6
votes
2answers
1k views

Length of longest palindrome subsequence

I had an interview, where I was asked to solve to this question: Given an string str, find the maximum length of palindrome subsequence. Example: >if str = 'abcda': maximum_length = 3 '...
6
votes
3answers
471 views

ChessMetric - Topcoder Challenge

My solution for the topcoder ChessMetric challenge seems really slow. I feel like there should be a better way, but I'm not sure. Challenge Description Suppose you had an n by n chess board ...
6
votes
1answer
242 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 ...
6
votes
1answer
1k views

Longest common subsequence length and backtracking the string

Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “...
6
votes
2answers
2k views

Finding the rod pieces in the rod cut issue

I have been reading the chapter 15 of "Introduction to Algorithms" (3rd edition) by Cormen, etc. The chapter 15 is about dynamic programming, and the first example they show us is the "rod cut problem"...
6
votes
1answer
3k views

Coin change algorithm

I've implemented the coin change algorithm using Dynamic Programming and Greedy Algorithm w/ backtracking. The description is as follows: Given an amount of change (n) list all of the possibilities ...
6
votes
2answers
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 ...
5
votes
2answers
1k views

Change-making problem with specific constraints

I am a new Pythoner. I have solved a OJ project with Python. Can you tell me how can I solve it more Pythonically? Problem Description: There are n coin denominations, each with an unlimited ...
5
votes
3answers
234 views

Largest contiguous sub-array sum

Challenge Determine the largest contiguous sum of integers in a list. Specifications The first argument is a path to a file. The file contains multiple lines. Each line is a test case represented ...
5
votes
2answers
829 views

High execution time of LCS length program in Python2

I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise. It's quite simple and straightforward, just print out the length of the LCS. I submitted this code: ...
5
votes
1answer
575 views

Dynamic attribute key selector

I'm basically trying to build a function that searches all nodes on the DOM to check for data attributes, then swap them out with whatever is stored with the "data-intl-" attribute. For example, if ...
5
votes
2answers
4k views

Optimizing O(m n) solution for longest common subsequence challenge

Given two strings string X of length x1 and string Y of length ...