Maximum sum such that no two elements are adjacent

Problem Statement : Given an array of numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Link: https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

Hint:

One of three for current index in a for loop 

1. best at (i-2) added to current

2. best at (i-1)

3. current only

Online Judge Link : https://practice.geeksforgeeks.org/problems/stickler-theif/0

Solution:

Rod Cutting Problem

Problem Statement: Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6).

GFG Link: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/

Practice Link: https://practice.geeksforgeeks.org/problems/rod-cutting/0

Solution:

Getting postorder traversal of a binary tree from inorder and preorder traversal

Problem Statement: Given inorder and preorder traversal of a binary tree, find its postorder traversal.

GFG Link : https://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/

Solution:

Matrix Chain Multiplication

Problem Statement: Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. There are many options to multiply a chain of matrices because matrix multiplication is associative i.e. no matter how one parenthesize the product, the result will be the same.

GfG Link : https://practice.geeksforgeeks.org/problems/matrix-chain-multiplication/0

Solution:

Similar to Parenthesization DP http://www.codebytes.in/2019/01/parenthesization-dp-problem.html

Shortest Common Supersequence

Problem Statement : https://www.geeksforgeeks.org/shortest-common-supersequence/

Solution:

Printing the Longest Common Subsequence

Problem Statement: Given two strings, print their longest common subsequence.

GFG Link : https://www.geeksforgeeks.org/printing-longest-common-subsequence/

Solution:

Output:

1
AGGTAB GXTXAYB

4 3 3 2 2 0 0 
4 3 3 2 2 1 1 
0 3 3 2 2 1 1 
0 3 3 2 2 1 1 
0 2 2 2 2 1 1 
0 1 1 1 1 1 1 

len = 4
0, 0
1, 0
2, 1
2, 2
3, 2
4, 3
4, 4
5, 5
5, 6
GTAB

Parenthesization DP Problem

Problem Statement : https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/

Solution (Bottom-Up DP):

01 Knapsack Problem

Problem Statement:

Source : https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

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).

Solution:

Maximum sum path in matrix

Problem statement : Given a N X N  matrix Matrix[N][N] of positive integers.  There are only three possible moves from a cell Matrix[r][c].

1. Matrix[r+1][c]

2. Matrix[r+1][c-1]

3. Matrix[r+1][c+1]

Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.

GeeksForGeeks link : https://practice.geeksforgeeks.org/problems/path-in-matrix/0

Algorithm : DP

Solution:

Ways to cover distance, DP

Problem Statement (https://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/):

Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.

Examples :

Input:  n = 3
Output: 4

Below are the four ways
 1 step + 1 step + 1 step
 1 step + 2 step
 2 step + 1 step
 3 step

Input:  n = 4
Output: 7

Explanation:

If we know the number of ways to reach the distances k-3, k-2, k-1, then the kth distance is just 3, 2 and 1 hops away respectively. So dp[k] = dp[k-3] + dp[k-2] + dp[k-1]

Code:

Minimum Sum Partition Problem

Statement: Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

Geeksforgeeks problem link : https://practice.geeksforgeeks.org/problems/minimum-sum-partition/0

Solution Explanation:

Simple recursive solution might be :

From index 0 start including each element into either of the partitions and recurse for the next index.
This is exponential complexity O(2^n)

What we can do is start from index 0. We either include it in first or second partition. For next index in the function call we include weight of first and second partition. When it reaches the end index it has a certain first partition and second partition sum and returns the difference between them. The indices previous to this receive the difference as return value and check to see if including the current index to the first or second partition gives overall less difference at the last index, given the current weight supplied by previous index.

A particular function call state is defined by the sum of first/second partition elements and the index we are seeing.

solve(int index, int firstPartitionSum, int secondPartitionSum)

DP[Index][FirstPartitionSum]

Code: