Contents tagged with dynamic programming

  • DP Intro

    Tags: dynamic programming, algorithms

    Four steps of dynamic programming, Characterize the structure of an optimal solution. Recursively define th evalue of an optimal solution. Compute the value of an optimal solution, typically in a … more

  • Longest Increasing Subsequence

    Tags: algorithms, dynamic programming

    Introduction Longest Increasing subsequence is called LIS in short. Intro to Algorithms, CLR, 3rd ed, p397: Ex-15.4-6 asks, Give an O(n^2)-time algorithm to find the longest monotonically … more

  • Longest Common Subsequence

    Tags: algorithms, dynamic programming

    Longest Common Sub-sequence is called LCS in short. The Problem Consider these two strings ( sequences of characters), A B C D A C D B We are to find the common strings/sub-sequences of them. … more

  • codeforces 455 A Boredom

    Tags: algorithms, dynamic programming

    The solution I have developed is a dynamic programming twist. From the problem specification it is obvious to see that we can run a loop upto 10^5 and calculate max points using a recurrence … more