Top 50 Dynamic Programming Java Algorithms Coding Questions (Udemy.com)

Welcome to this course!

Here, you will go through a "journey" of the Top 50 Dynamic Programming Java Algorithm questions that are asked in coding interviews as well as competitive programming.

So let's start by answering the most fundamental questions:

What is Dynamic Programming Algorithm?

Dynamic programming is a powerful optimization technique for plain recursion problems. If you can break down a problem into simpler sub-problems (optimal substructure) and these sub-problems are repetitive in nature, then you can convert this problem into a Dynamic Programming Solution.

In this course, we will start with a basic introduction to Dynamic Programming. We will understand what Dynamic Programming is and how to find out whether a recursive problem can be solved using Dynamic Programming.

Can Dynamic Programming solve all problems?

Dynamic Programming cannot solve all problems. The dynamic programming algorithm is meant to solve only those problems that have optimal substructure and overlapping subproblem properties.

Why is Dynamic Programming faster?

Dynamic Programming is faster because we break down a problem into various smaller subproblems. Then, we store the solutions of these subproblems in a table or cache whenever we encounter them first. Hence, if we get the same subproblem later on, instead of recomputing it, we fetch it from the storage and return it. This saves us a lot of time.

Moreover, since a Dynamic Programming algorithm required optimal substructure property. It means that the best solution to the initial subproblem can be constructed from the optimal solutions of its subproblems. Hence, we can easily eliminate the need to consider all the possible subproblem solutions. This reduces the time complexity of the algorithm.

What will be our approach when you take this course?

We will solve the 50 most popular Dynamic Programming examples asked in coding interviews. For each question, our approach will be:

• Understand the problem statement with a few examples.

• Check if it can be solved recursively.

• Build a recursion tree and determine the recursive pattern.

• Check for optimal substructure and overlapping subproblem properties using the recursive tree.

• Derive the recursive code for the solution.

• Using the recursive code, convert the problem to a Top-Down (Memoization) approach.

• Then solve the same problem with the Bottom-Up (Tabulation) approach.

• Come up with an optimized DP solution if possible (space or time).

• Discuss the time and space complexities of all the approaches.

Don't worry, we won't bore you with slides and PPTs. We will understand each algorithm using a whiteboard explanation of approaches and the code in parallel. This will help you to be more expressive during your interviews.

In any interview, the interviewer wants to know the thinking or the approach that you are going to take to solve a problem given by him. Thus, it becomes very necessary to keep reciting the approach out loud. The format of these videos will help you to think out loud and will promote discussions and you will be able to question back the interviewer.

What are the top 50 Dynamic Programming Problems or Examples asked in Coding Interview and Competitive Programming that we will discuss?

Lecture 1: Introduction

Lecture 2: Introduction to Dynamic Programming - Recursive, Memoization, Tabulation

Lecture 3: Binomial Coefficient Problem

Lecture 4: Maximize the Cut Segments

Lecture 5: Friends Pairing Problem

Lecture 6: Rod Cutting Problem

Lecture 7: Gold Mine Problem

Lecture 8: Nth Catalan Number

Lecture 9: Largest Sum Contiguous SubArray (Kadane's Algorithm)

Lecture 10: Climbing Stairs

Lecture 11: Maximum Sum Increasing Subsequence

Lecture 12: House Robber

Lecture 13: Subset Sum Problem

Lecture 14: Longest Common Subsequence

Lecture 15: Longest Increasing Subsequence

Lecture 16: Weighted Job Scheduling

Lecture 17: Maximum Length Chain of Pairs

Lecture 18: Maximum Sum of Disjoint Pairs with Specific Differences

Lecture 19: Egg-Dropping Problem

Lecture 20: Minimum Removals from Array to make Max - Min <= K (DP + Binary Search)

Lecture 21: Maximum Size Square Sub-Matrix with all 1s

Lecture 22: Largest Area Rectangular Sub-Matrix with Equal 0's and 1's

Lecture 23: Largest Rectangular Sub-Matrix whose Sum is 0

Lecture 24: Maximum Sum Rectangle in a 2D Matrix

Lecture 25: Longest Palindromic Subsequence

Lecture 26: Longest Palindromic Substring

Lecture 27: Longest Alternating Subsequence

Lecture 28: Count All Palindromic Subsequences in a Given String

Lecture 29: Longest Common Substring

Lecture 30: Longest Subsequence such that the Difference Between Adjacent is 1

Lecture 31: Longest Repeated Subsequence

Lecture 32: Word Break Problem

Lecture 33: Permutation Coefficient Problem

Lecture 34: Minimum Number of Jumps to Reach End

Lecture 35: Partition Problem

Lecture 36: Count Derangements

Lecture 37: Count the Number of Ways to Reach a Given Score in a Game

Lecture 38: Palindromic Partitioning

Lecture 39: Matrix Chain Multiplication

Lecture 40: Maximum Subsequence Sum such that no 3 Elements are Consecutive

Lecture 41: Painting the Fence

Lecture 42: Largest Independent Set of Nodes in a Binary Tree

Lecture 43: Count Balanced Binary Trees of Height H

Lecture 44: Coin Change Problem

Lecture 45: Optimal Strategy for a Game

Lecture 46: Unique Paths

Lecture 47: Minimum Cost Path

Lecture 48: Coin Game Winner Where Every Player Has 3 Choices

Lecture 49: Edit Distance