Skip to content

Pavankumardontha/dynamic-programming-

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

148 Commits
0-1knapsack.cpp
0-1knapsack.cpp
 
 
2_keys_keyboard(DP).cpp
2_keys_keyboard(DP).cpp
 
 
2_keys_keyboard(recur).cpp
2_keys_keyboard(recur).cpp
 
 
Caesar's Legions.cpp
Caesar's Legions.cpp
 
 
CoinCombinations-1.cpp
CoinCombinations-1.cpp
 
 
CoinCombinations-2.cpp
CoinCombinations-2.cpp
 
 
CoinCombinations-3.cpp
CoinCombinations-3.cpp
 
 
CombinationSum-1.cpp
CombinationSum-1.cpp
 
 
CombinationSum-2.cpp
CombinationSum-2.cpp
 
 
CombinationSum-3.cpp
CombinationSum-3.cpp
 
 
CombinationSum-4.cpp
CombinationSum-4.cpp
 
 
ConsecutiveOnesNotAllowed.cpp
ConsecutiveOnesNotAllowed.cpp
 
 
CountNo.OfWaysToReachNthStair.cpp
CountNo.OfWaysToReachNthStair.cpp
 
 
CountPossibleWaysToConstructBuildings.cpp
CountPossibleWaysToConstructBuildings.cpp
 
 
CountWaysfromTopleftToBottomRight.cpp
CountWaysfromTopleftToBottomRight.cpp
 
 
Delete_operations_for_2_strings(DP).cpp
Delete_operations_for_2_strings(DP).cpp
 
 
Delete_operations_for_2_strings(recur).cpp
Delete_operations_for_2_strings(recur).cpp
 
 
DiceCombinations(CSES).cpp
DiceCombinations(CSES).cpp
 
 
Distinct Subsequences
Distinct Subsequences
 
 
Edit_distance(DP).cpp
Edit_distance(DP).cpp
 
 
Edit_distance(recur).cpp
Edit_distance(recur).cpp
 
 
House_robber.cpp
House_robber.cpp
 
 
JumpGame-1.cpp
JumpGame-1.cpp
 
 
JumpGame-2.cpp
JumpGame-2.cpp
 
 
JumpGame-3.cpp
JumpGame-3.cpp
 
 
JumpGame-4.cpp
JumpGame-4.cpp
 
 
Kadanes.cpp
Kadanes.cpp
 
 
Length of Longest bitonic subsequence
Length of Longest bitonic subsequence
 
 
LongestCommonSubsequence(DP).cpp
LongestCommonSubsequence(DP).cpp
 
 
LongestCommonSubsequence(recursion).cpp
LongestCommonSubsequence(recursion).cpp
 
 
LongestCommonsubstring.cpp
LongestCommonsubstring.cpp
 
 
LongestPathInDirectedAcyclicGraph.cpp
LongestPathInDirectedAcyclicGraph.cpp
 
 
Longest_increasing_subsequence.cpp
Longest_increasing_subsequence.cpp
 
 
Max_k_coins_from_piles.cpp
Max_k_coins_from_piles.cpp
 
 
MaximizeCutSegments.cpp
MaximizeCutSegments.cpp
 
 
Maximum sum bitonic Subsequence
Maximum sum bitonic Subsequence
 
 
MaximumTipCalculator.cpp
MaximumTipCalculator.cpp
 
 
Maximum_path_sum_matrix.cpp
Maximum_path_sum_matrix.cpp
 
 
Maximum_sum_problem.cpp
Maximum_sum_problem.cpp
 
 
Min_ascii_delete(DP).cpp
Min_ascii_delete(DP).cpp
 
 
Min_ascii_delete(recur).cpp
Min_ascii_delete(recur).cpp
 
 
MinimumCoinsToMakeChange.cpp
MinimumCoinsToMakeChange.cpp
 
 
Minimum_white_tiles_after_covering_with_carpets.cpp
Minimum_white_tiles_after_covering_with_carpets.cpp
 
 
N-length_vowels_sorted.cpp
N-length_vowels_sorted.cpp
 
 
No.ofSubsetsWithGivenSum.cpp
No.ofSubsetsWithGivenSum.cpp
 
 
OptimalGameStrategy.cpp
OptimalGameStrategy.cpp
 
 
PalindromePartitioning-2.cpp
PalindromePartitioning-2.cpp
 
 
PalindromePartitioning-3.cpp
PalindromePartitioning-3.cpp
 
 
PalindromePartitioning-4.cpp
PalindromePartitioning-4.cpp
 
 
PotsOfGold.cpp
PotsOfGold.cpp
 
 
README.md
README.md
 
 
Repeat_Permutations.cpp
Repeat_Permutations.cpp
 
 
Repeat_combinations.cpp
Repeat_combinations.cpp
 
 
Rod_cutting.cpp
Rod_cutting.cpp
 
 
Yet another Broken keyboard-codeforces
Yet another Broken keyboard-codeforces
 
 
buy_and_sell_2(recursive_dp).cpp
buy_and_sell_2(recursive_dp).cpp
 
 
buy_and_sell_2.cpp
buy_and_sell_2.cpp
 
 
buy_and_sell_multiple_transactions.cpp
buy_and_sell_multiple_transactions.cpp
 
 
buy_and_sell_multiple_transactions_with_cooldown.cpp
buy_and_sell_multiple_transactions_with_cooldown.cpp
 
 
buy_and_sell_multiple_transactions_with_fee.cpp
buy_and_sell_multiple_transactions_with_fee.cpp
 
 
buy_and_sell_one_transaction.cpp
buy_and_sell_one_transaction.cpp
 
 
buy_and_sell_stocks(atmost_2_transactions).cpp
buy_and_sell_stocks(atmost_2_transactions).cpp
 
 
buy_and_sell_stocks(atmost_k_transactions).cpp
buy_and_sell_stocks(atmost_k_transactions).cpp
 
 
egg dropping problem
egg dropping problem
 
 
max_absolute_sum_of_any_subarray.cpp
max_absolute_sum_of_any_subarray.cpp
 
 
nth_stair_atmost_k_steps.cpp
nth_stair_atmost_k_steps.cpp
 
 
skip the work(dp,recursive).cpp
skip the work(dp,recursive).cpp
 
 
subset sum
subset sum
 
 

Repository files navigation

Problem Set

  1. Count all possible ways from top left to bottom right.
  2. Path with minimum Effort(leetcode dijshiktra on 2D grid)
  3. Count N-length strings consisting only of vowels sorted lexographically.
  4. Reach Nth stair
  5. Nth stair with atmost K steps
  6. Reach a given score-- very very imp --(https://practice.geeksforgeeks.org/problems/reach-a-given-score-1587115621/1)
  7. Maximum path sum in matrix(GFG :- https://practice.geeksforgeeks.org/problems/path-in-matrix3805/1)
  8. Maximum sum Problem(https://practice.geeksforgeeks.org/problems/maximum-sum-problem2211/1#)
  9. Find minimum/maximum cost of the path from any cell in the first row to any cell in the last row.
  10. Longest increasing subsequence (NlogN , DP )
  11. Longest subsequence such that difference between adjacent elements is one.
  12. https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
  13. Longest Bitonic Subsequence
  14. Longest sum Bitonic Subsequence
  15. Maximum sum subarray
  16. Kadanes Algorithm(Maximum sum subarray)
  17. Maximum Absolute Sum of Any Subarray
  18. Skip the work(direct dp solution and converting the recursive program into dp)
  19. Yet another broken keyboard-codeforces
  20. Caesar's Legions codeforces
  21. Flower eating marmot
  22. Optimal game strategy
  23. Pots of gold game
  24. Maximum Tip Calculator
  25. 0-1 Knapsack
  26. 0-1 knapsack unbounded
  27. Coin Combinations-1(Permutations taken into account. 1D problem with outer loop running on the sum)
  28. Coins Combinations-2(only Combinations are taken into account.1D problem with inner loop running on the sum)
  29. No. of subsets with given sum(Inner loop running on sum. Understand why ?? 2D similar to 0-1 knapsack)
  30. No. of subsets with given sum(1D with inner loop running on sum but reversed)
  31. Partial Equal Subset sum(1D problem correlate with above problems)
  32. Count Ways to reach Nth stair
  33. Minimum No. of coins to make a change.
  34. Maximize the cut segments
  35. Dice Combinations(CSES)
  36. Rod cutting Problem(maximum profit problem)
  37. Consecutive 1's not allowed
  38. House robber - 1 (recursion + DP leetcode)
  39. House robber - 2 (recursion + DP leetcode)
  40. Count possible ways to construct Buildings
  41. Longest Path in Directed Acyclic graph
  42. Buy and sell stocks(one transaction allowed) - I
  43. Buy and sell stocks(multiple transactions) - II (refer recursive and iterative and analyse why dp cannot be used in this problem)
  44. Buy and sell stocks(multiple transactions) with cooldown
  45. Buy and sell stocks(multiple transactions) with transaction fee
  46. Buy and sell stocks(atmost 2 transactions)
  47. Buy and sell stocks(atmost k transactions)
  48. 2 keys keyboard (recursion + DP)
  49. Edit distance (recursion + DP)
  50. Minimum White Tiles After Covering With Carpets (recursion + DP leetcode)
  51. Delete Operation for Two Strings (recursion + DP)
  52. Minimum ascii delete sum to make 2 strings same (recursion + DP)
  53. Partition equal subset sum (leetcode , recursion + DP)
  54. Word break problem (leetcode)
  55. Partition with k equal subset sum (leetcode , Can be done only with backtracking)
  56. Given an array of size N in how many ways you can get a sum of k using elements of the array.
  57. No repetition + Combinations
  58. No repetition + Permutations
  59. Repetition + Combinations ( CSES coin Combination - 2 )
  60. Repetition + Permutations ( CSES Coin Combination - 1 )
  61. Combination sum - 1 (leetcode)
  62. Combination sum - 2 (leetcode very important)
  63. Combination sum - 3 (leetcode)
  64. Combination sum - 4 (leetcode)
  65. Palindrome partitioning - 1 (backtracking , leetcode)
  66. Palindrome partitioning - 2 ( DP , leetcode )
  67. Palindrome partitioning - 3 ( DP , leetcode )
  68. Palindrome partitioning - 4 ( DP , leetcode )
  69. Maximum Value of K Coins From Piles (leetcode)
  70. Jump Game - 1 (leetcode)
  71. Jump Game - 2 (leetcode can be done using BFS and also DP)
  72. Jump Game - 3 (leetcode-BFS)
  73. Jump Game - 4 (leetcode-BFS)

Combinations and Permutations counting problems

Given an input array and a target value , the possible type of problems that we face are listed below. Array restriction output

  1. distinct elements + taken only once + Combinations ( combination sum - 3 )
  2. Distinct elements + taken any times + Combinations ( coin combinations - 2 , combination sum - 1 )
  3. Distinct elements + taken only once + Permutations
  4. Distinct elements + taken any times + Permutations ( combination sum - 4 , coin combinations - 1 )
  5. Repetition of elements + taken only once + Combinations ( combination sum - 2 )
  6. Repetition of elements + taken any times + Combinations
  7. Repetition of elements + taken only once + Permutations
  8. Repetition of elements + taken any times + Permutations

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages