Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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
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 ...
0
votes
2answers
422 views

Code for calculating number of trailing zeroes after factorial

While trying my hands at the beginner codechef problem I came across this . So basically doing that problem with Dynamic programming is an overkill but why not try that and get some DP practice. Nice,...
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 ...
1
vote
1answer
275 views

Simple Factor Class

I have a class which lazily factors numbers. It provides the user with these methods: getFactors returns a ...
1
vote
1answer
1k views

Knapsack 01 solution

Solution to bounded knapsack 01 problem. Once again comprehensive description is difficult in this space, refer here. Looking for code review. optimizations and best practices. ...
3
votes
2answers
145 views

Count the number of ways to obtain a sum, with consecutivity restriction

A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary. ...
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 ...
3
votes
1answer
327 views

Number of unique sequences of 3 digits, given a length is equal to sum

This is the "Minion's bored game" problem from Google's "Foobar challenge": There you have it. Yet another pointless "bored" game created by the bored minions of Professor Boolean. The game is ...
2
votes
1answer
497 views

Longest Increasing Sub-Sequence using Dynamic Programming in Python

I wrote the following function to find the longest increasing sub-sequence in an array (tuple, it doesn't work for a list since a list is mutable and it stores the results in a dictionary.). It uses ...
2
votes
0answers
317 views

Shortest bitonic tour

This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to ...
4
votes
2answers
1k views

Rod-Cutting Problem using dynamic programming

I wrote the following code for solving the Rod-Cutting Problem using dynamic programming: Rod Cutting Problem: Given a rod of length n inches and an array of prices that contains prices of all ...
1
vote
0answers
297 views

Longest palindrome subsequence

This algorithm finds the longest palindrome that is a subsequence of a given input string in \$\Theta(n^2)\$. Example Input: character Output: ...
0
votes
2answers
348 views

google foo.bar max path algorithm puzzle optimization [closed]

I got a programming puzzle described as follows: Save Beta Rabbit Oh no! The mad Professor Boolean has trapped Beta Rabbit in an NxN grid of rooms. In the center of each room (except for the ...
0
votes
1answer
43 views

Loading URLs via a case statement

I have the following code which loads in a URL based on the id of a user-clicked button. I'm looking to compress it down as much as possible, and make it more modular and reusable: ...
2
votes
2answers
3k views

Candie distribution algorithm

I am studying algorithms and I solved this problem under Dynamic Programming section: Alice is a kindergarten teacher. She wants to give some candies to the children in her class. All the ...
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 ...
5
votes
2answers
835 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: ...
2
votes
2answers
73 views

Find the best path amongst N random points

For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points. I wanted to use a dynamic ...
4
votes
1answer
7k views

Determining maximum profit to be made from selling shares

Question Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next \$N\$ days. Each ...
1
vote
1answer
2k views

Levenshtein distance with edit sequence and alignment in Java

I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment: LevenshteinEditDistance.java: ...
5
votes
2answers
370 views

Number of ways to make change for an amount

Task Write a program that, given the amount to make change for and a list of coins prints out how many different ways you can make change from the coins to STDOUT. My approach The number to make ...
2
votes
1answer
174 views

0-1 Knapsack in Java

I'm looking for advice on coding practices in general. ...
2
votes
1answer
84 views

Optimally allocating a resource with time-varying demand and cost

I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
2
votes
1answer
892 views

Auto registering class registry

I built this auto registering registry to look into a package and import all modules and register any classes that are a subclass of a base class. I use it as a registry for a model's choices in ...
4
votes
1answer
2k views

Finding the longest path, avoiding obstacles in a 2D plane

The Scenario You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
0
votes
1answer
851 views

Longest contiguous Increasing Subset in java

I have tried to come up with a solution to the longest increasing subsequence problem.Can this solution be optimized further? Example 1: Input: {5,4,3,7,8,9,11} Output: 3, 7, 8, 9, 11 Example 2: ...
3
votes
1answer
1k views

Subset sum whose set contains only positive integers

I was trying to write a dynamic programming algorithm using a bottom up approach that solves the subset sum problem's version where the solution can be either an empty set and the initial set can only ...
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\$....
4
votes
5answers
793 views

Pass Triangle challenge

In order to solve this challenge: Challenge Description By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27. <...
4
votes
2answers
2k views

Optimal matrix chain multiplication in Java

Preliminaries Given two matrices $$ A = \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1q} \\ a_{21} & a_{22} & \dots & a_{2q} \\ \vdots & \vdots & \ddots & \vdots \\...
3
votes
1answer
806 views

Dynamic Programming for printing additive numbers up to digits n

Edit: I am hoping to get some review / make sure I am understanding dynamic programming correctly. I am trying to print out all additive numbers up to digits n using dynamic programming. Additive ...
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 ...
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 ...
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} &...
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 ...
2
votes
1answer
79 views

Construct biggest stacked tower with restriction

Problem The problem is to build the tallest tower made up of cylinders, respecting all the rules. Will be arranged on the table, an amount of \$N\$ cylinders. Each cylinder has one color: Red, ...
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"...
4
votes
1answer
1k views

HackerRank - Candies

Here is the solution I've written for Hacker Rank Candies challenge. It uses dynamic programming (memoization in a boxed array). I'm interested on what could be done to improve this code in term of ...
6
votes
3answers
472 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 ...
4
votes
1answer
315 views

AvoidRoads - TopCoder Challenge

I'm learning Dynamic Programming, following the topcoder guide. I just solved the AvoidRoads challenge. It passes all the test cases, but I don't have much experience, so I don't know if it's good. ...
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 ...
2
votes
2answers
547 views

BadNeighbors - Topcoder puzzle

I'm learning Dynamic Programming, following the topcoder guide. I just solved the BadNeighbors puzzle. It passes all the test cases, but I don't have much experience, so I don't know if it's good. ...
3
votes
3answers
162 views

Max contiguous slice in Ruby

I need to compute the max contiguous slice in an array. I wrote this function, but I am not sure if it is correct or I am missing edge cases. I ran several cases. ...
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, ...
2
votes
1answer
7k views

Implementation of Sequence Alignment in C++

Below is my implementation of the dynamic programming solution to the sequence alignment problem in C++11: ...
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 ...
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 ...
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 ...
4
votes
4answers
9k views

Find the minimum number of coins

I'm trying to learn dynamic programming and the most popular one is to find the minimum number of coins for the change. I come up with this but I just want to improve this code which I think it could ...
5
votes
1answer
99 views

Optimal way to annihilate a list by removing items from the ends

I'm stuck with a contest problem. Description: What is the minimum number of moves to annihilate an int array where the possible moves are: Remove both the first and last elements if they are equal ...