EduBhogi Video Demo

Stolen

"Three minutes to the train," thought Rakesh. It had been a tiring day for him. His job at the dockyard, which was initially hard on him, had gotten easier with time. Earlier, it was a strange caricature of decay and resurrection, but after his first salary was credited a few days ago, the same structure turned into the sweaty smell of hope. Somehow, he had found a home in the blood-metal sound of machines and the ocean's blue water and skies. He did not particularly enjoy coming to the railway station, though. The railway station always made him envious of the lives other people had—families saying affectionate goodbyes, girlfriends holding hands with their boyfriends, and a group of young men cackling with laughter and merriment. It was this envy that made him buy an expensive new smartphone with his first salary. He wanted to feel more confident among the crowd around him. He had already imagined himself standing beside the pole of the Mumbai local train, earphones in his ears, and the wind blowing through his hair. The fact that he owned such an expensive piece of technology made him beam with happiness and joy. He had touched his front pocket jeans countless times, partly because he wanted to be sure that he had one and partly just to enjoy its feel in his pocket. 

"Pooooo..." whistled the train. Rakesh looked up toward the arriving train. Finally, he was going home. He raised his suitcase over his head so that he could fight his way into the general coach of the train. It's amazing to see how quickly people coalesce to get into the general coach of the train. Rakesh nudged around with his elbows as he tried to get on board. In the midst of elbow-kicking and chest foreplay, he saw the familiar face of Mr. Patloo. Mr. Patloo was a 40-year-old man with five strands of hair on his head. He wore a colorful T-shirt and tight-fitted jeans. You did not have to look closely to understand that he was a textbook example of midlife crisis. Oblivious to his bizarre sense of fashion, Mr. Patloo greeted Rakesh with a wide, affectionate smile as both of them fought their way through the crowd. Somehow, they were lucky enough to be inside the train. The general coach of the bogie is a different type of caricature in itself. As you pass, you can smell the different body odors mixed on the bogie.

Dynamic Programming

In this blog post we will discuss various dynamic programming questions. The idea is to have a same template to understand all the dynamic programming problems. All the problems that we discuss will be divided into four parts:-

• What is the question?  (read * 2 times) 
• Why this problem can be solved with the help of Dynamic Programming? (read once)
• What does dp[i][j] or dp[i] mean with respect to the question? (read once)
• What is the solution if the assumed dp array is to be constructed? (read once)
• How the dp[i] or dp[i][j] will be formulated? Along with the help of an example. (read twice)
• Variations to the questions 

Once these algorithms are done, we will observe that even the new problems can be solved with the help of this template. I have used same terminology to make the questions easier. 

1. Longest Common Subsequnce

QUESTION : Given two sequences, find the length of longest subsequence present in both of them. In the code given below we assume X,Y to be strings.

WHY DP:  Notice that given problem can be broken down as smaller chunk problem. Let us just take the first character of both the strings and compare them. Then we take the next character of string 1 and compare it with string 2 and so on.

DP[i][j]: 
for the string s1[0..i] and string s2[0..j] what is the length of longest common subsequence with those specific substrings.  Example let string 1 be  "abcdefg" anf string 2 be "abcdgk"

SOLUTION:   dp[n][m] (initialized as  dp[n+1][m+1]

CODE:
https://github.com/vaibhavgeek/tompetitive/blob/master/dynamicProgramming/lcs.cpp

        if (i == 0 || j == 0)  
            dp[i][j] = 0;  

        else if (X[i - 1] == Y[j - 1])  
            dp[i][j] = dp[i - 1][j - 1] + 1;  

        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

Variations:- 

• Printing Longest Common Subsequence
• Longest Common Subsequence with at most k changes allowed

 2. Maximum Sum Subarray

Tha maximum sum subarray is the task of finding the largest possible sum of a contagious subarray, within a given one-dimensional array A[1..n]. (No length specified)

    dp[i] = max(dp[i-1] + a[i] , a[i])

The maximum subarray problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers with k length.

    dp[i] = dp[i-1] + a[i] - a[i-k-1]

3. Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

    if(arr[j] < arr[i])
        dp[i] = max(dp[i], dp[j] + 1)

4. KnapSack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property)
In this problem we define dp[i][j] as i value and for j knapsack capacity. That is for j capacity how much maximum value it can store.

if( j < wt[i]) 
        dp[i][j] = dp[i-1][j];
    else 
        dp[i][j] = max(dp[i-1][j - wt[i]] + val[i] , dp[i-1][j]);

5. Coinchange Problem

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

    if(j >= coin[i])
     {
        dp[i][j] = min(1 + dp[i][j-coin[i]] , dp[i-1][j]);
     }
     else
     {
           dp[i][j] = dp[i-1][j];
     }

5. Wordbreak Problem