Skip to content

skm2000/Dynamic-Programming

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

96 Commits
spoj
spoj
 
 
.gitignore
.gitignore
 
 
3_segment.cpp
3_segment.cpp
 
 
Best_Time_To_Buy_And_Sell_Stock_.cpp
Best_Time_To_Buy_And_Sell_Stock_.cpp
 
 
BitonicSequence.cpp
BitonicSequence.cpp
 
 
Box_Stacking_Problem.cpp
Box_Stacking_Problem.cpp
 
 
Circular_Kadene.cpp
Circular_Kadene.cpp
 
 
Coin_Changing_1.cpp
Coin_Changing_1.cpp
 
 
Coin_Changing_2.cpp
Coin_Changing_2.cpp
 
 
Count_All_Increasing_Subsequences.cpp
Count_All_Increasing_Subsequences.cpp
 
 
Count_All_Pallindromic_Subsequence.cpp
Count_All_Pallindromic_Subsequence.cpp
 
 
Count_Distinct_Subsequences.cpp
Count_Distinct_Subsequences.cpp
 
 
Count_Number_of_hops.cpp
Count_Number_of_hops.cpp
 
 
Count_Pallindromic_SubString_Of_String_gfg.cpp
Count_Pallindromic_SubString_Of_String_gfg.cpp
 
 
Count_Subsets_of_given_Sum.cpp
Count_Subsets_of_given_Sum.cpp
 
 
Count_ways_to_N'th_Stair.cpp
Count_ways_to_N'th_Stair.cpp
 
 
Diameter_Of_Binary_Tree.cpp
Diameter_Of_Binary_Tree.cpp
 
 
Distinct_Occurences.cpp
Distinct_Occurences.cpp
 
 
Edit_Distance.cpp
Edit_Distance.cpp
 
 
Equal_Sum_Partition.cpp
Equal_Sum_Partition.cpp
 
 
Friends_Pairing_Problem.cpp
Friends_Pairing_Problem.cpp
 
 
Get_Minimum_Squares.cpp
Get_Minimum_Squares.cpp
 
 
GoldMine_Problem.cpp
GoldMine_Problem.cpp
 
 
Jump_Game_3.cpp
Jump_Game_3.cpp
 
 
Jump_Game_5.cpp
Jump_Game_5.cpp
 
 
Kadane.cpp
Kadane.cpp
 
 
Knapsack_0_1.cpp
Knapsack_0_1.cpp
 
 
Last_Stone_3.cpp
Last_Stone_3.cpp
 
 
Longest_Common_Subsequence.cpp
Longest_Common_Subsequence.cpp
 
 
Longest_Common_Substring.cpp
Longest_Common_Substring.cpp
 
 
Longest_Consequetive_Subsequence.cpp
Longest_Consequetive_Subsequence.cpp
 
 
Longest_Decreasing_Subsequence.cpp
Longest_Decreasing_Subsequence.cpp
 
 
Longest_Increasing_Subsequence.cpp
Longest_Increasing_Subsequence.cpp
 
 
Longest_Pallindromic_Subsequence.cpp
Longest_Pallindromic_Subsequence.cpp
 
 
Longest_Pallindromic_Substring.cpp
Longest_Pallindromic_Substring.cpp
 
 
Longest_Repeating_Subsequence.cpp
Longest_Repeating_Subsequence.cpp
 
 
Matrix_Chain_Multiplication.cpp
Matrix_Chain_Multiplication.cpp
 
 
Max_Path_Sum_in_Triangle.cpp
Max_Path_Sum_in_Triangle.cpp
 
 
Max_path_sum.cpp
Max_path_sum.cpp
 
 
Maximize_the_cutting.cpp
Maximize_the_cutting.cpp
 
 
Maximum_Dot_Product_Subsequence.cpp
Maximum_Dot_Product_Subsequence.cpp
 
 
Maximum_Path_Sum_in_Binary_tree.cpp
Maximum_Path_Sum_in_Binary_tree.cpp
 
 
Maximum_Product_Increasing_Subsequence.cpp
Maximum_Product_Increasing_Subsequence.cpp
 
 
Maximum_Size_Submatrix_Square.cpp
Maximum_Size_Submatrix_Square.cpp
 
 
Maximum_Sum_Decreasing_Subsequence.cpp
Maximum_Sum_Decreasing_Subsequence.cpp
 
 
Maximum_Sum_Dividing_Recurssive.cpp
Maximum_Sum_Dividing_Recurssive.cpp
 
 
Maximum_Sum_Increasing_Subsequence.cpp
Maximum_Sum_Increasing_Subsequence.cpp
 
 
Maximum_length_of_pairs.cpp
Maximum_length_of_pairs.cpp
 
 
Minimum_Ascii_Sum_deletion_To_Make_two_Strings_equal.cpp
Minimum_Ascii_Sum_deletion_To_Make_two_Strings_equal.cpp
 
 
Minimum_Initial_Points_To_Reach_Destinaion.cpp
Minimum_Initial_Points_To_Reach_Destinaion.cpp
 
 
Minimum_Jumps_To_Reach_End.cpp
Minimum_Jumps_To_Reach_End.cpp
 
 
Minimum_Subset_Sum_Difference.cpp
Minimum_Subset_Sum_Difference.cpp
 
 
Minm_Cost_To_Fill_Bag.cpp
Minm_Cost_To_Fill_Bag.cpp
 
 
Minm_Deletion_To_Make_Pallindrome.cpp
Minm_Deletion_To_Make_Pallindrome.cpp
 
 
Minm_Insertion_Deletion_Convert.cpp
Minm_Insertion_Deletion_Convert.cpp
 
 
No_Of_Ways_To_Tile.cpp
No_Of_Ways_To_Tile.cpp
 
 
Number_of_ways_to_decode_a_string.cpp
Number_of_ways_to_decode_a_string.cpp
 
 
Optimal_Strategy_To_Play_A_Game.cpp
Optimal_Strategy_To_Play_A_Game.cpp
 
 
Path_In_A_Matrix.cpp
Path_In_A_Matrix.cpp
 
 
Print_Longest_Common_Subsequence.cpp
Print_Longest_Common_Subsequence.cpp
 
 
Procuct_of_array_except_self.cpp
Procuct_of_array_except_self.cpp
 
 
README.md
README.md
 
 
Reach_a_given_score.cpp
Reach_a_given_score.cpp
 
 
Rod_Cutting.cpp
Rod_Cutting.cpp
 
 
Russian_Doll_Envelope.cpp
Russian_Doll_Envelope.cpp
 
 
Shortest_Common_Supersequence.cpp
Shortest_Common_Supersequence.cpp
 
 
SubsetSum.cpp
SubsetSum.cpp
 
 
Tiling_Problem.cpp
Tiling_Problem.cpp
 
 
Unbounded_Knapsack.cpp
Unbounded_Knapsack.cpp
 
 
Uncrossed_Lines.cpp
Uncrossed_Lines.cpp
 
 
count_submatrices_with_all_ones.cpp
count_submatrices_with_all_ones.cpp
 
 
count_subsets_of_given_difference.cpp
count_subsets_of_given_difference.cpp
 
 
flip_game_1.cpp
flip_game_1.cpp
 
 
flip_game_2.cpp
flip_game_2.cpp
 
 
jump_game_2..cpp
jump_game_2..cpp
 
 
longest_alternating_subsequence.cpp
longest_alternating_subsequence.cpp
 
 
maximal_square.cpp
maximal_square.cpp
 
 
maximum_product_subarray.cpp
maximum_product_subarray.cpp
 
 
maximum_sum_submatrix.cpp
maximum_sum_submatrix.cpp
 
 
minm_number_of_taps_to_open_water.cpp
minm_number_of_taps_to_open_water.cpp
 
 
nim_game.cpp
nim_game.cpp
 
 
nth_catlan_number.cpp
nth_catlan_number.cpp
 
 
num_products.cpp
num_products.cpp
 
 
number_of_permutations_such_that_no_three_forms_increasing_sequence.cpp
number_of_permutations_such_that_no_three_forms_increasing_sequence.cpp
 
 
number_of_valid_parenthesis.cpp
number_of_valid_parenthesis.cpp
 
 
unique_paths_1.cpp
unique_paths_1.cpp
 
 
unique_paths_2.cpp
unique_paths_2.cpp
 
 
video_stiching.cpp
video_stiching.cpp
 
 
zerosAndOnes.cpp
zerosAndOnes.cpp
 
 

Repository files navigation

Dynamic-Programming

A DP a day keeps the bug away.

Cointains Dp Problems

Parent Problem : Kadane's Algorithm

  1. Best Time to Buy and sell Stock(Leetcode)
  2. Circular Kadane

Parent Problem : Fibonacci.
SubProblems :

  1. Reach a given Score.
  2. Count number of hops.
  3. Count ways to reach n-th stair.
  4. Count Number of Ways to Tile.
  5. Tiling Problem-General.
  6. Maximum Sum Dividing.
  7. Friends Pairing Problem
  8. Maximize the Cutting
  9. Number of Ways to Decode a String

Parent Problem : 0/1 KnapSack Problem
SubProblems :

  1. SubSet Sum.
  2. Equal Sum Partition.
  3. Count of SubSet Sum.
  4. Minimum SubSet Sum Difference.
  5. Count SubSets of given Sum.

Parent Problem : Unbounded KnapSack
SubProblems :

  1. Coin Changing Problem 1(No of ways).
  2. Coin Changing Problem 2(Minimum no of coins).
  3. Rod Cutting Problem.
  4. Minimum Cost to Fill Bag.

Parent Problem : Longest Common SubSequence
SubProblems :

  1. Longest Common SubString.
  2. Shortest Common SuperSequence.
  3. Print LCS.
  4. Minimum Insertions And Deletion to Convert a String.
  5. Longest Repeating SubSequence.
  6. Longest Pallindromic SubSequence.
  7. Edit Distance.
  8. Count All Pallindromic SubSequence.
  9. Minimum Deletion to make string pallindrome.
  10. Count Distinct Occcurences.
  11. Maximum length of pairs.
  12. Minimum Ascii Sum deletion To Make two Strings equal.
  13. Maximum Dot Product of Subsequences(Leetcode).
  14. Uncrossed Lines(LeetCode).

Parent Problem : Longest Increasing Subsequence

  1. Russian Doll Envelope(Leetcode).
  2. Longest Decreasing SubSequence.
  3. Maximum Sum Increasing SubSequence.
  4. Maximum Sum Decreasing SubSequence.
  5. Maximum Product Increasing Subsequence.
  6. Minimum Jumps to reach end.
  7. Box Stacking Problem.
  8. Longest Bitonic Sequence.
  9. Longest Alternating Subsequence
  10. Count All Increasing Subsequences.

Parent Problem : DP + Greedy

  1. Jump Game-2(Leetcode).
  2. Video Stiching(Leetcode).
  3. Minm number of taps to open water.

Parent Problem : Game(DP) + minimax

  1. Nim Game.
  2. Flip Game-1.
  3. Flip Game-2.
  4. Get Minimum Squares.
  5. Optimal Strategy to play a Game.
  6. Stone Game-3
  7. Jump Game-3(Leetcode)
  8. Jump Game-5(Leetcode)

Parent Problem : Dp on Grids

  1. Maximum Size Submatrix Square.
  2. Maximum Path Sum in Triangle.
  3. Minimum Initial Points to Reach Destination.
  4. GoldMine Problem
  5. Path in a Matrix
  6. Maximal Square(Leetcode)
  7. Count Submatrices with all ones(Leetcode)
  8. Maximum Sum Submatrix
  9. Unique Path-1
  10. Unique Path-2

Parent Problem : Matrix Chain Multiplication

Parent Problem : Count Distinct SubSequences

Parent Problem : Dp on Trees

  1. Max Path Sum
  2. Maximum Path Sum in a Tree from Any node to any other node
  3. Diameter of a Binary Tree

Others

  1. Longest Consequetive Subsequences.
  2. Zeroes And Ones
  3. Longest Pallidromic SubString.
  4. Count Pallindromic substring of string
  5. Product of array except self

Happy Coding!!

About

A DP a day keeps the bug away.

Resources

Readme
Activity

Stars

208 stars

Watchers

10 watching

Forks

62 forks
Report repository

Contributors 3

  •  
  •  
  •  

Languages