# Questions tagged [dynamic-programming]

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

298 questions
Filter by
Sorted by
Tagged with
1k 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 ... ...
• 501
781 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 ...
• 171
447 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 ...
• 1,796
252 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 ...
• 306
110 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 ...
• 291
61 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 ...
904 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 ...
• 175
1 vote
1k 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 ...
2k 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 ...
• 268
1 vote
994 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-...
1k 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 ...
1 vote
90 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 ...
• 19
2k 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: ...
771 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 ...
• 2,469
2k 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. <...
• 2,469
10k 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 ...
• 143
410 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 ...
• 1,080
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 ...
920 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 ...
127 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 ...
1k 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 ...
• 255
461 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 ...
• 121
2k 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 <...
• 3,490
943 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 ...
79 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 minimum ...
• 7,159
63 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 ...
• 31
4k 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 ...
• 178
145 views

• 283
430 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$ ...
• 261
1k views

### minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
• 737
90 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 ...
• 737
975 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 ...
• 163