Dynamic Programming Playlist | Interview Questions | C++ | DSA

FreeProgramming
  • 6.5K likes on YouTube
  • 350.9K views

Created by Apna College

  • 8 chapters
  • 3.9h
  • Hindi

What you'll learn

  • Core idea and optimized recursion
  • DSA • Dynamic programming basics
  • 1D DP fundamentals
  • DSA • Dynamic programming
  • Optimal Substructure
  • Algorithms • Knapsack Problem Types
  • 0/1 Knapsack Definition
  • Overlapping subproblems

Explore related topics

Course content

8 chapters · 3.9h total length
  1. 01Complete Dynamic Programming | DP Series - Lecture 1Preview41:33

    This chapter introduces Dynamic Programming (DP) as an optimized form of recursion, using the Fibonacci sequence as the running example. A naive recursive Fibonacci has exponential time complexity because the same subproblems (such as F(2) and F(3)) are recomputed many times, drawn as a recursion tree with repeated branches. DP avoids this by storing results of subproblems the first time they are computed and reusing them later. Storing these results in a separate array, the Fibonacci solution drops to linear time, which is why DP is also called optimized recursion.

    • Core idea and optimized recursion
    • Overlapping subproblems
    • Optimal substructure
    • Memoization vs tabulation
    • Fibonacci with DP
    • DP patterns
  2. 02DP 2. Climbing Stairs | 1D Dynamic ProgrammingPreview26:26

    This chapter covers the Climbing Stairs problem (LeetCode 70), a classic 1D dynamic programming problem. You start on the ground and must reach the top of n stairs, taking either one step or two steps at a time. The task is to count the distinct ways to reach the top. Small cases show the pattern: n = 1 gives 1 way, n = 2 gives 2 ways, n = 3 gives 3 ways, and n = 4 gives 5 ways. The key insight is that after taking one step, the remaining problem is n-1, and after taking two steps, it is n-2. So the number of ways is f(n) = f(n-1) + f(n-2), with base cases f(1) = 1 and f(2) = 2. This is the same recurrence as Fibonacci.

    • DSA • Dynamic programming basics
    • DSA • Recurrence relations
    • DSA • Overlapping subproblems and optimal substructure
    • DSA • Memoization
    • DSA • Tabulation (bottom-up DP)
    • DSA • Space optimisation in DP
  3. 03DP 3. House Robber | 1D Dynamic ProgrammingPreview25:43

    This chapter solves LeetCode 198, House Robber, using 1D dynamic programming. A robber can rob houses in a row, each holding a non-negative amount of money, but cannot rob two adjacent houses. The goal is to find the maximum total amount that can be stolen. For the example array [2, 7, 9, 3, 1], the answer is 12 (rob houses with values 2, 9 and 1).

    • 1D DP fundamentals
    • Overlapping subproblems and optimal substructure
    • House Robber recurrence
    • Tabulation and base cases
    • Space optimisation to O(1)
  4. 04DP 4. House Robber II | 1D Dynamic ProgrammingPreview22:30

    This chapter solves LeetCode 213, House Robber II, using dynamic programming. The setup is a row of houses, each holding an amount of money. You may not rob two adjacent houses, and because the houses are arranged in a circle, the first and last houses are also adjacent. The goal is to find the maximum money that can be collected under these rules. The chapter builds on the straight-line House Robber I problem, whose core recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]): for each house, either skip it and keep the best answer so far, or rob it and add it to the best answer two houses back.

    • DSA • Dynamic programming
    • DSA • House Robber II (circular array)
    • DSA • Tabulation (bottom-up DP)
    • DSA • Space optimization in DP
    • DSA • Reducing a circular problem to two linear problems
  5. 05DP 5. Frog Jump | 1D Dynamic ProgrammingPreview29:29

    This chapter solves the Frog Jump problem, a 1D dynamic programming problem. A frog starts on stair 0 and can jump one or two stairs at a time. The cost of each jump is the absolute difference in height between the two stairs it connects. The goal is the minimum total cost to reach the last stair.

    • DSA • Dynamic programming basics
    • DSA • Frog Jump problem
    • DSA • 1D DP tabulation
    • DSA • Overlapping subproblems and optimal substructure
    • DSA • Space optimization in DP
  6. 06DP 6. Min Cost Climbing Stairs | 1D Dynamic ProgrammingPreview26:08

    This chapter explores the 'Minimum Cost Climbing Stairs' problem, a classic variation of the climbing stairs dynamic programming challenge. The objective is to reach beyond the top of a staircase with minimum cost, where each step has an associated price to pay upon crossing it. You can jump either one or two steps at a time and have the flexibility to start at either index 0 or index 1. The problem is framed around the core principles of dynamic programming: overlapping subproblems and optimal substructure.

    • Optimal Substructure
    • Tabulation Method
    • Algorithms • Time and Space Complexity
    • Space Optimization
    • Overlapping Subproblems
  7. 07Fractional Knapsack Algorithm | Greedy MethodPreview16:33

    The fractional knapsack problem is a classic optimization challenge where the goal is to maximize the total value of items placed in a bag (knapsack) with a fixed weight capacity. Unlike the 0/1 knapsack problem, where items must be taken whole or not at all, the fractional version allows you to take parts of items. This characteristic makes it suitable for a greedy algorithmic approach, which seeks the best local choice at each step to reach a global optimum.

    • Algorithms • Knapsack Problem Types
    • Algorithms • Greedy Method
    • Data Structures • Fractional Knapsack Implementation
    • Computational Complexity • Time Complexity Analysis
  8. 08DP 8. 0/1 Knapsack | Recursion to DP Solution | Space OptimizedPreview45:03

    This chapter provides a comprehensive exploration of the 0/1 Knapsack problem, a fundamental pattern in dynamic programming. The problem involves a collection of items, each with a specific weight and value, and a knapsack with a limited weight capacity. The goal is to select a subset of items to maximize the total value without exceeding the capacity. The '0/1' nature of the problem dictates that each item must be taken in its entirety or not at all, distinguishing it from fractional knapsack problems which are typically solved with greedy algorithms.

    • 0/1 Knapsack Definition
    • Recursive Approach
    • Overlapping Subproblems
    • Memoization (Top-Down)
    • Tabulation (Bottom-Up)
    • Complexity Analysis

About the creator

Apna College

The videos in this course are made by Apna College and play from YouTube, credited to them. Studyio adds the chapters, notes, quizzes and a certificate around them.

More courses like this