Top 50 Dynamic Programming Java Algorithms Coding Questions

Solve the top 50 Dynamic Programming Java Algorithms Questions to ace Coding Interview and Competitive Programming.

What you'll learn

Understand what is Dynamic Programming, Recursion, and back tracking

Learn the criteria to classify a dynamic programming question using optimal substructure and overlapping subproblems

Master the art of recursion and learn how to convert a recursion problem to dynamic programming

Solve top 50 handpicked dynamic programming Java algorithm questions asked in competitive programming and programming interviews

Solve each question in recursive, top-down (memoization) and bottom-up (tabulation) dynamic programming approaches

Get one step closer to competitive programming and acing coding interview

Requirements

Understanding of any basic programming language (preferably Java)

Basics of programming language such as variables, loops, conditionals, arrays, and strings

Basic understanding of time and space complexities

Description

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 question - What is Dynamic Programming?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. What will be our approach when you take this course?We will solve the 50 most popular Dynamic Programming coding interview questions. 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 Coding Interview Questions that we will discuss?Lecture 1: IntroductionLecture 2: Introduction to Dynamic Programming - Recursive, Memoization, TabulationLecture 3: Binomial Coefficient ProblemLecture 4: Maximize the Cut SegmentsLecture 5: Friends Pairing ProblemLecture 6: Rod Cutting ProblemLecture 7: Gold Mine ProblemLecture 8: Nth Catalan NumberLecture 9: Largest Sum Contiguous SubArray (Kadane's Algorithm)Lecture 10: Climbing StairsLecture 11: Maximum Sum Increasing SubsequenceLecture 12: House RobberLecture 13: Subset Sum ProblemLecture 14: Longest Common SubsequenceLecture 15: Longest Increasing SubsequenceLecture 16: Weighted Job SchedulingLecture 17: Maximum Length Chain of PairsLecture 18: Maximum Sum of Disjoint Pairs with Specific DifferencesLecture 19: Egg-Dropping ProblemLecture 20: Minimum Removals from Array to make Max - Min <= K (DP + Binary Search)Lecture 21: Maximum Size Square Sub-Matrix with all 1sLecture 22: Largest Area Rectangular Sub-Matrix with Equal 0's and 1'sLecture 23: Largest Rectangular Sub-Matrix whose Sum is 0Lecture 24: Maximum Sum Rectangle in a 2D MatrixLecture 25: Longest Palindromic SubsequenceLecture 26: Longest Palindromic SubstringLecture 27: Longest Alternating SubsequenceLecture 28: Count All Palindromic Subsequences in a Given StringLecture 29: Longest Common SubstringLecture 30: Longest Subsequence such that the Difference Between Adjacent is 1Lecture 31: Longest Repeated SubsequenceLecture 32: Word Break ProblemLecture 33: Permutation Coefficient ProblemLecture 34: Minimum Number of Jumps to Reach EndLecture 35: Partition ProblemLecture 36: Count DerangementsLecture 37: Count the Number of Ways to Reach a Given Score in a GameLecture 38: Palindromic PartitioningLecture 39: Matrix Chain MultiplicationLecture 40: Maximum Subsequence Sum such that no 3 Elements are ConsecutiveLecture 41: Painting the FenceLecture 42: Largest Independent Set of Nodes in a Binary TreeLecture 43: Count Balanced Binary Trees of Height HLecture 44: Coin Change ProblemLecture 45: Optimal Strategy for a GameLecture 46: Unique PathsLecture 47: Minimum Cost PathLecture 48: Coin Game Winner Where Every Player Has 3 ChoicesLecture 49: Edit DistanceLecture 50: 0/1 Knapsack ProblemLecture 51: Find if a String is Interleaved with 2 Other StringsLecture 52: Maximum Profit by Buying and Selling a Share at Most TwiceThese questions are taken from popular practice websites and hence, are asked in coding interviews of top tech companies like Google, Apple, IBM, Cisco, Atlassian, Microsoft, etc. In each of these questions, not only you will learn just about the algorithm to solve those questions, but you will also learn about other concepts like working with HashMaps, HashSets, sorting an array of objects using comparators, binary search algorithms, trees, etc. You will be able to understand the basics of Java programming language and other data structures as well.Having said this, let's meet in the first lecture on "Introduction to Dynamic Programming".

Overview

Section 1: Introduction

Lecture 1 Introduction

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

Section 2: Binomial Coefficient Problem

Lecture 3 Binomial Coefficient Problem

Section 3: Maximize the Cut Segments

Lecture 4 Maximize the Cut Segments

Section 4: Friends Pairing Problem

Lecture 5 Friends Pairing Problem

Section 5: Rod Cutting Problem

Lecture 6 Rod Cutting Problem

Section 6: Gold Mine Problem

Lecture 7 Gold Mine Problem

Section 7: Nth Catalan Number

Lecture 8 Nth Catalan Number

Section 8: Largest Sum Contiguous SubArray (Kadane's Algorithm)

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

Section 9: Climbing Stairs

Lecture 10 Climbing Stairs

Section 10: Maximum Sum Increasing Subsequence

Lecture 11 Maximum Sum Increasing Subsequence

Section 11: House Robber

Lecture 12 House Robber

Section 12: Subset Sum Problem

Lecture 13 Subset Sum Problem

Section 13: Longest Common Subsequence

Lecture 14 Longest Common Subsequence

Section 14: Longest Increasing Subsequence

Lecture 15 Longest Increasing Subsequence

Section 15: Weighted Job Scheduling

Lecture 16 Weighted Job Scheduling

Section 16: Maximum Length Chain of Pairs

Lecture 17 Maximum Length Chain of Pairs

Section 17: Maximum Sum of Disjoint Pairs with Specific Difference

Lecture 18 Maximum Sum of Disjoint Pairs with Specific Difference

Section 18: Egg Dropping Problem

Lecture 19 Egg Dropping Problem

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

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

Section 20: Maximum Size Square Sub-Matrix with all 1s

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

Section 21: Largest Area Rectangular Sub-Matrix with Equal 0's and 1's

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

Section 22: Largest Rectangular Sub-Matrix whose Sum is 0

Lecture 23 Largest Rectangular Sub-Matrix whose Sum is 0

Section 23: Maximum Sum Rectangle in a 2D Matrix

Lecture 24 Maximum Sum Rectangle in a 2D Matrix

Section 24: Longest Palindromic Subsequence

Lecture 25 Longest Palindromic Subsequence

Section 25: Longest Palindromic Substring

Lecture 26 Longest Palindromic Substring

Section 26: Longest Alternating Subsequence

Lecture 27 Longest Alternating Subsequence

Section 27: Count All Palindromic Subsequence in a Given String

Lecture 28 Count All Palindromic Subsequence in a Given String

Section 28: Longest Common Substring

Lecture 29 Longest Common Substring

Section 29: Longest Subsequence such that Difference Between Adjacent is 1

Lecture 30 Longest Subsequence such that Difference Between Adjacent is 1

Section 30: Longest Repeated Subsequence

Lecture 31 Longest Repeated Subsequence

Section 31: Word Break Problem

Lecture 32 Word Break Problem

Section 32: Permutation Coefficient Problem

Lecture 33 Permutation Coefficient Problem

Section 33: Minimum Number of Jumps to Reach End

Lecture 34 Minimum Number of Jumps to Reach End

Section 34: Partition Problem

Lecture 35 Partition Problem

Section 35: Count Derangements

Lecture 36 Count Derangements

Section 36: Count Number of Ways to Reach a Given Score in a Game

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

Section 37: Palindromic Partitioning

Lecture 38 Palindromic Partitioning

Section 38: Matrix Chain Multiplication

Lecture 39 Matrix Chain Multiplication

Section 39: Maximum Subsequence Sum such that no 3 Elements are Consecutive

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

Section 40: Painting the Fence

Lecture 41 Painting the Fence

Section 41: Largest Independent Set of Nodes in a Binary Tree

Lecture 42 Largest Independent Set of Nodes in a Binary Tree

Section 42: Count Balanced Binary Trees of Height H

Lecture 43 Count Balanced Binary Trees of Height H

Section 43: Coin Change Problem

Lecture 44 Coin Change Problem

Section 44: Optimal Strategy for a Game

Lecture 45 Optimal Strategy for a Game

Section 45: Unique Paths

Lecture 46 Unique Paths

Section 46: Minimum Cost Path

Lecture 47 Minimum Cost Path

Section 47: Coin Game Winner Where Every Player has 3 Choices

Lecture 48 Coin Game Winner Where Every Player has 3 Choices

Section 48: Edit Distance

Lecture 49 Edit Distance

Section 49: 0/1 Knapsack Problem

Lecture 50 0/1 Knapsack Problem

Section 50: Find if a String is Interleaved of 2 Other Strings

Lecture 51 Find if a String is Interleaved of 2 Other Strings

Section 51: Maximum Profit by Buying and Selling a Share at most Twice

Lecture 52 Maximum Profit by Buying and Selling a Share at most Twice

Students or professionals who are preparing for software developer related coding interview,Programmers who want to get into competitive programming,Self-taught programmers who want to learn data structures and algorithms