# Dynamic programming interview questions

### Count of binary strings without consecutive 1’s

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example, Input: N = 2 Output: 3. Explanation: There ...

### Optimal Binary Search Trees

BSTs are used to organize a set of search keys for fast access: the tree maintains the keys in-order so that comparison with the query at any node either results ...

### Largest sum of non-adjacent numbers

Given an array of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.For example, Input: [2, 4, 6, 2, 5] Output: ...

### Is subsequence

Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original ...

### Cutting rods problem

Given a rod of length ‘n’ units and list of prices of pieces of lengths ‘1’ to ‘n’, the problem is to determine the maximum value that can be obtained ...

### Digit sum of n-digit numbers

Find the count of n-digit numbers whose sum of digits is equal to given sum s. For example, Input: n=2 and s=5 Output: 14, 23, 32, 41, 50 Explanation: we ...

### Super Egg drop problem

Egg dropping problem goes like given n eggs and f floors, our task is to find the minimum number of trials required to find the highest floor from which it ...

### Climbing the staircase

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 2 steps at a time, in how many ...

### Fibonacci series and dynamic programming

Find nth Fibonacci number Given a Fibonacci series: 1, 1, 2, 3, 5, 8, 13 ... which is defined as fib(n) = fib(n-1) + fib(n-2), find Nth number in this ...

### Fill 4xN wall with 4×1 and 1×4 bricks

Fill 4xN wall with 4x1 and 1x4 bricks There is a wall with 4 x N dimensions and we have a brick with 4 x 1 dimension. We have to ...