pyPython Practice LabFrom first print to final round
TOPIC 17 OF 18

Dynamic Programming Python practice problems

State design, recurrences, memoization, tabulation, optimization, and overlapping subproblems.

22 exercises8+ conceptsBeginner → interview context
Start this topic
WHAT YOU WILL PRACTISE

Core concepts

Count ways to climb stairsMaximize nonadjacent house lootFind minimum coinsSolve 0/1 knapsackFind longest increasing subsequence lengthFind longest common subsequence lengthCalculate edit distancePartition values into equal sums
REUSABLE THINKING

Problem-solving patterns

  • dynamic programming · Fibonacci
  • house robber · DP
  • coin change · bottom-up DP
  • knapsack · space optimization
  • LIS · binary search
PRACTICE OUTCOME

What this topic builds

Learn the idea once, use it across the exercises, and explain why your approach works.

ORDERED PRACTICE

All 22 problems in this topic

Work from top to bottom to build the concept gradually.

  1. #327
    Count ways to climb stairs: Five stairs

    Count different one-step and two-step sequences that reach stair five.

    BeginnerPremium
  2. #328
    Count ways to climb stairs: Zero stairs

    There is one way to remain at the starting point: take no steps.

    BeginnerPremium
  3. #329
    Maximize nonadjacent house loot: Alternating opportunity

    Find the maximum value without choosing adjacent houses.

    IntermediatePremium
  4. #330
    Maximize nonadjacent house loot: Two houses

    Choose the larger value when the only two houses are adjacent.

    IntermediatePremium
  5. #331
    Find minimum coins: Reachable amount

    Find the fewest coins needed to make eleven.

    IntermediatePremium
  6. #332
    Find minimum coins: Impossible amount

    Return -1 when no combination can form the requested amount.

    IntermediatePremium
  7. #333
    Solve 0/1 knapsack: Choose best package

    Maximize value under a small carrying capacity.

    IntermediatePremium
  8. #334
    Solve 0/1 knapsack: No item fits

    Return zero when every item is heavier than the capacity.

    AdvancedPremium
  9. #335
    Find longest increasing subsequence length: Mixed sequence

    Find the LIS length in a common interview example.

    AdvancedPremium
  10. #336
    Find longest increasing subsequence length: Strictly decreasing

    Only one value can belong to a strictly increasing subsequence.

    AdvancedPremium
  11. #337
    Find longest common subsequence length: Shared subsequence

    Find the LCS length for two strings with characters in common order.

    AdvancedPremium
  12. #338
    Find longest common subsequence length: No common characters

    Return zero when the strings share no character.

    AdvancedPremium
  13. #339
    Calculate edit distance: Classic conversion

    Find the minimum edits needed to convert kitten to sitting.

    AdvancedPremium
  14. #340
    Calculate edit distance: Empty target

    Deleting every source character is optimal when the target is empty.

    AdvancedPremium
  15. #341
    Partition values into equal sums: Equal partition exists

    Determine that the values can be split into two equal-sum groups.

    Interview-LevelPremium
  16. #342
    Partition values into equal sums: Equal partition impossible

    Return False when no subset reaches half of the total.

    Interview-LevelPremium
  17. #343
    Segment a string into dictionary words: Segmentable text

    Check whether the complete string can be split into dictionary entries.

    Interview-LevelPremium
  18. #344
    Segment a string into dictionary words: Near match fails

    Reject a string whose final characters cannot be covered by the dictionary.

    Interview-LevelPremium
  19. #345
    Count numeric message decodings: Several decodings

    Count all A-to-Z interpretations of a digit string.

    Interview-LevelPremium
  20. #346
    Count numeric message decodings: Leading zero

    A message beginning with zero has no valid decoding.

    Interview-LevelPremium
  21. #347
    Count unique paths with obstacles: One central obstacle

    Count right-and-down routes that avoid a blocked cell.

    Interview-LevelPremium
  22. #348
    Count unique paths with obstacles: Start blocked

    Return zero when the starting cell is blocked.

    Interview-LevelPremium