Dynamic Programming Problems Guide
Dynamic Programming Problems Guide
1
Contents
2
Contents
42 Balanced expressions such that given positions have opening brackets 384
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
3
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
55 Choose maximum weight with given weight and value ratio 460
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
57 Coin game winner where every player has three choices 475
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
4
Contents
72 Count all possible paths from top left to bottom right of a mXn matrix 576
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582
76 Count binary strings with k times appearing adjacent two set bits 603
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
5
Contents
79 Count even length binary sequences with same sum of first and second
half bits 620
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
93 Count of arrays in which all adjacent elements are such that one of them
divide the another 720
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
95 Count of n digit numbers whose sum of digits equals to given sum 730
6
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
101 Count the number of ways to tile the floor of size n x m using 1 x m
size tiles 778
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784
102 Count total number of N digit numbers such that the difference be-
tween sum of even and odd digits is 1 785
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787
105 Count ways to increase LCS length of two strings by one 798
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801
106 Count ways to reach the nth stair using step 1, 2 or 3 802
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
109 Counting pairs when a person can form pair with at most one 831
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
7
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856
112 Different ways to sum n using numbers greater than or equal to m 857
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861
122 Efficient program to print all prime factors of a given number 918
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 924
126 Find Maximum dot product of two arrays with insertion of 0’s 947
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950
127 Find all combinations of k-bit numbers with n bits set where 1 <= n
<= k in sorted order 951
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 953
8
Contents
129 Find all distinct subset (or subsequence) sums of an array 961
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968
130 Find all distinct subset (or subsequence) sums of an array | Set-2 969
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971
134 Find length of the longest consecutive path from a given starting char-
acter 991
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 999
135 Find longest bitonic sequence such that increasing and decreasing parts
are from two different arrays 1000
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1002
138 Find maximum sum array of length less than or equal to m 1022
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1023
140 Find minimum number of coins that make a given value 1032
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1043
141 Find minimum possible size of array with given rules for removing
elements 1044
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1047
142 Find minimum sum such that one of every three consecutive elements
is taken 1048
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1054
9
Contents
148 Find the largest area rectangular sub-matrix whose sum is equal to k 1099
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1103
149 Find the longest path in a matrix with given constraints 1104
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1108
150 Find the minimum cost to reach destination using a train 1109
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1119
151 Find the probability of reaching all points after N moves from point N1120
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1122
152 Finding the maximum square sub-matrix with all equal elements 1123
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1132
10
Contents
161 How to print maximum number of A’s using given four keys 1194
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1203
169 Largest area rectangular sub-matrix with equal number of 1’s and 0’s 1265
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1269
11
Contents
185 Longest Even Length Substring such that Sum of First and Second
Half is same 1370
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1382
12
Contents
201 Longest subsequence such that difference between adjacents is one 1478
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1485
204 Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l 1504
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1506
207 Maximize the sum of selected numbers from an array to make it empty 1528
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1530
210 Maximum Subarray Sum using Divide and Conquer algorithm 1546
13
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1553
212 Maximum absolute difference between sum of two contiguous sub-arrays 1560
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1571
217 Maximum difference of zeros and ones in binary string | Set 2 (O(n)
time) 1600
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1605
223 Maximum path sum for each position with jumps under divisibility
condition 1633
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1639
225 Maximum path sum that starting with any cell of 0-th row and ending
with any cell of (N-1)-th row 1647
14
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1652
226 Maximum points collected by two persons allowed to meet once 1653
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1656
227 Maximum points from top left of matrix to bottom right and return
back 1657
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1662
229 Maximum profit by buying and selling a share at most k times 1668
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1681
230 Maximum profit by buying and selling a share at most twice 1682
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1691
234 Maximum sub-matrix area having count of 1’s one more than count of
0’s 1711
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1715
236 Maximum subarray sum in an array created after repeated concatenation 1724
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1730
237 Maximum subsequence sum such that no three are consecutive 1731
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1738
241 Maximum sum in a 2 x n grid such that no two elements are adjacent1769
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1772
15
Contents
242 Maximum sum in circular array such that no two elements are adjacent 1773
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1776
243 Maximum sum increasing subsequence from a prefix and a given ele-
ment after prefix is must 1777
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1782
249 Maximum sum such that no two elements are adjacent 1826
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1831
250 Maximum value with the choice of either dividing or considering as it is 1832
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1836
251 Maximum weight path ending at any element of last row in a matrix 1837
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1843
255 Minimum Cost Path with Left, Right, Bottom and Up moves allowed 1864
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1867
16
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1885
262 Minimum cells required to reach destination with jumps equal to cell
values 1906
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1914
265 Minimum cost to make two strings identical by deleting the digits 1925
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1930
266 Minimum cost to reach the top of the floor by climbing stairs 1931
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1941
267 Minimum cost to sort strings using reversal operations of different costs 1942
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1946
17
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1992
276 Minimum number of jumps to reach end | Set 2 (O(n) solution) 2010
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2017
277 Minimum number of single digit primes required whose sum is equal
to N 2018
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2026
278 Minimum number of squares whose sum equals to given number n 2027
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2038
279 Minimum removals from array to make max – min <= K 2039
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2048
280 Minimum splits in a binary string such that every substring is a power
of 4 or 6. 2049
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2054
287 Minimum sum subsequence such that at least one of every four con-
secutive elements is picked 2097
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2104
288 Minimum time to finish tasks without skipping two consecutive 2105
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2114
289 Minimum time to write characters using insert, delete and copy operation 2115
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2117
18
Contents
298 Number of Co-prime pairs obtained from the sum of digits of elements
in the given range 2180
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2186
300 Number of Unique BST with a given key | Dynamic Programming 2191
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2196
301 Number of arrays of size N whose elements are positive integers and
sum is K 2197
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2202
302 Number of circular tours that visit all petrol pumps 2203
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2206
303 Number of decimal numbers of length k, that are strict monotone 2207
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2212
19
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2231
308 Number of ordered pairs such that (Ai & Aj) = 0 2240
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2247
311 Number of paths from source to destination in a directed acyclic graph 2261
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2264
318 Number of ways a convex polygon of n+2 sides can split into triangles
by connecting vertices 2301
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2306
321 Number of ways to form an array with distinct adjacent elements 2315
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2324
322 Number of ways to insert a character to increase the LCS by one 2325
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2328
20
Contents
323 Number of ways to reach Nth floor by taking at-most K leaps 2329
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2336
328 Partition a set into two subsets such that the difference of subset sums
is minimum 2359
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2367
329 Partitioning into two contiguous element subarrays with equal sums 2368
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2371
331 Perfect Sum Problem (Print all subsets with given sum) 2378
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2383
21
Contents
340 Print all possible ways to convert one string into another string | Edit-
Distance 2441
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2449
341 Print equal sum sets of array (Partition Problem) | Set 2 2450
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2459
342 Print equal sum sets of array (Partition problem) | Set 1 2460
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2473
22
Contents
360 Queries to find distance between two nodes of a Binary tree 2593
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2595
362 Remove array end element to maximize the sum of product 2603
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2604
363 Remove minimum elements from either side such that 2*min becomes
more than max 2605
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2610
367 Sequences of given length where every element is more than or equal
to twice of previous 2640
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2650
370 Shortest path with exactly k edges in a directed and weighted graph 2670
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2676
23
Contents
375 Smallest length string with repeated replacement of two distinct adjacent 2706
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2711
376 Smallest number with given sum of digits and sum of square of digits 2712
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2715
24
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2804
390 Super Ugly Number (Number whose prime factors are in given set) 2805
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2808
402 Total number of possible Binary Search Trees and Binary Trees with
n keys 2885
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2895
403 Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming) 2896
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2897
404 Traversal of tree with k jumps allowed between nodes of same height 2898
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2903
25
Contents
409 Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree) 2934
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2939
412 Ways to arrange Balls such that adjacent balls are of different types 2945
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2958
413 Ways to sum to N using array elements with repetition allowed 2959
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2963
26
Chapter 1
DP-01 | Overlapping
Subproblems Property in
Dynamic Programming
27
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
We can see that the function fib(3) is being called 2 times. If we would have stored the
value of fib(3), then instead of computing it again, we could have reused the old stored value.
There are following two different ways to store the values so that these values can be reused:
a) Memoization (Top Down)
b) Tabulation (Bottom Up)
a) Memoization (Top Down): The memoized program for a problem is similar to the
recursive version with a small modification that it looks into a lookup table before computing
solutions. We initialize a lookup array with all initial values as NIL. Whenever we need the
solution to a subproblem, we first look into the lookup table. If the precomputed value is
there then we return that value, otherwise, we calculate the value and put the result in the
lookup table so that it can be reused later.
Following is the memoized version for nth Fibonacci Number.
C/C++
28
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
{
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}
return lookup[n];
}
int main ()
{
int n = 40;
_initialize();
printf("Fibonacci number is %d ", fib(n));
return 0;
}
Java
29
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
}
public static void main(String[] args)
{
Fibonacci f = new Fibonacci();
int n = 40;
f._initialize();
System.out.println("Fibonacci number is" + " " + f.fib(n));
}
}
// This Code is Contributed by Saket Kumar
Python
C#
30
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
using System;
class GFG
{
static int MAX = 100;
static int NIL = -1;
static int []lookup = new int[MAX];
/* Function to initialize NIL
values in lookup table */
static void initialize()
{
for (int i = 0; i < MAX; i++)
lookup[i] = NIL;
}
/* function for nth Fibonacci number */
static int fib(int n)
{
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n - 1) + fib(n - 2);
}
return lookup[n];
}
// Driver code
public static void Main()
{
int n = 40;
initialize();
Console.Write("Fibonacci number is" + " " + fib(n));
}
}
// This Code is Contributed by Sam007
b) Tabulation (Bottom Up): The tabulated program for a given problem builds a table
in bottom up fashion and returns the last entry from table. For example, for the same
Fibonacci number, we first calculate fib(0) then fib(1) then fib(2) then fib(3) and so on. So
literally, we are building the solutions of subproblems bottom-up.
Following is the tabulated version for nth Fibonacci Number.
31
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
C/C++
Java
Python
32
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
C#
33
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
// This Code is Contributed by Sam007
PHP
<?php
// PHP program for Tabulated version
function fib($n)
{
$f[$n + 1]=0;
$i;
$f[0] = 0;
$f[1] = 1;
for ($i = 2; $i <= $n; $i++)
$f[$i] = $f[$i - 1] +
$f[$i - 2];
return $f[$n];
}
// Driver Code
$n = 9;
echo("Fibonacci number is ");
echo(fib($n));
// This code is contributed by nitin mittal.
?>
Output:
Fibonacci number is 34
Both Tabulated and Memoized store the solutions of subproblems. In Memoized version,
table is filled on demand while in Tabulated version, starting from the first entry, all entries
are filled one by one. Unlike the Tabulated version, all entries of the lookup table are not
necessarily filled in Memoized version. For example, Memoized solution of the LCS problem
doesn’t necessarily fill all entries.
To see the optimization achieved by Memoized and Tabulated solutions over the basic Re-
cursive solution, see the time taken by following runs for calculating 40th Fibonacci number:
Recursive solution
Memoized solution
Tabulated solution
Time taken by Recursion method is much more than the two Dynamic Programming tech-
niques mentioned above – Memoization and Tabulation!
34
Chapter 1. DP-01 | Overlapping Subproblems Property in Dynamic Programming
Also, see method 2 of Ugly Number post for one more simple example where we have
overlapping subproblems and we store the results of subproblems.
We will be covering Optimal Substructure Property and some more example problems in
future posts on Dynamic Programming.
Try following questions as an exercise of this post.
1) Write a Memoized solution for LCS problem. Note that the Tabular solution is given in
the CLRS book.
2) How would you choose between Memoization and Tabulation?
References:
http://www.youtube.com/watch?v=V5hZoJ6uK-s
Improved By : nitin mittal
Source
https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/
35
Chapter 2
36
Chapter 2. DP-02 | Optimal Substructure Property in Dynamic Programming
Source
https://www.geeksforgeeks.org/optimal-substructure-property-in-dynamic-programming-dp-2/
37
Chapter 3
More Examples:
38
Chapter 3. DP-03 | Longest Increasing Subsequence
Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such
that arr[i] is the last element of the LIS.
Then, L(i) can be recursively written as:
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.
To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Thus, we see the LIS problem satisfies the optimal substructure property as the main prob-
lem can be solved using solutions to subproblems.
Following is a simple recursive implementation of the LIS problem. It follows the recursive
structure discussed above.
C/C++
39
Chapter 3. DP-03 | Longest Increasing Subsequence
Java
40
Chapter 3. DP-03 | Longest Increasing Subsequence
if (n == 1)
return 1;
// 'max_ending_here' is length of LIS ending with arr[n-1]
int res, max_ending_here = 1;
/* Recursively get all LIS ending with arr[0], arr[1] ...
arr[n-2]. If arr[i-1] is smaller than arr[n-1], and
max ending with arr[n-1] needs to be updated, then
update it */
for (int i = 1; i < n; i++)
{
res = _lis(arr, i);
if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall max. And
// update the overall max if needed
if (max_ref < max_ending_here)
max_ref = max_ending_here;
// Return length of LIS ending with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
static int lis(int arr[], int n)
{
// The max variable holds the result
max_ref = 1;
// The function _lis() stores its result in max
_lis( arr, n);
// returns max
return max_ref;
}
// driver program to test above functions
public static void main(String args[])
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.length;
System.out.println("Length of lis is "
+ lis(arr, n) + "n");
}
}
41
Chapter 3. DP-03 | Longest Increasing Subsequence
Python
42
Chapter 3. DP-03 | Longest Increasing Subsequence
# lenght of arr
n = len(arr)
# maximum variable holds the result
maximum = 1
# The function _lis() stores its result in maximum
_lis(arr , n)
return maximum
# Driver program to test the above function
arr = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60]
n = len(arr)
print "Length of lis is ", lis(arr)
# This code is contributed by NIKHIL KUMAR SINGH
Length of lis is 5
Overlapping Subproblems:
Considering the above implementation, following is recursion tree for an array of size 4.
lis(n) gives us the length of LIS for arr[].
lis(4)
/ |
lis(3) lis(2) lis(1)
/ /
lis(2) lis(1) lis(1)
/
lis(1)
We can see that there are many subproblems which are solved again and again. So this
problem has Overlapping Substructure property and recomputation of same subproblems
can be avoided by either using Memoization or Tabulation. Following is a tabluated imple-
mentation for the LIS problem.
C/C++
43
Chapter 3. DP-03 | Longest Increasing Subsequence
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++ )
for (j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* Pick maximum of all LIS values */
for (i = 0; i < n; i++ )
if (max < lis[i])
max = lis[i];
/* Free memory to avoid memory leak */
free(lis);
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of lis is %dn", lis( arr, n ) );
return 0;
}
Java
44
Chapter 3. DP-03 | Longest Increasing Subsequence
Python
45
Chapter 3. DP-03 | Longest Increasing Subsequence
# Pick maximum of all LIS values
for i in range(n):
maximum = max(maximum , lis[i])
return maximum
# end of lis function
# Driver program to test above function
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print "Length of lis is", lis(arr)
# This code is contributed by Nikhil Kumar Singh
Output:
Length of lis is 5
Note that the time complexity of the above Dynamic Programming (DP) solution is O(n^2)
and there is a O(nLogn) solution for the LIS problem. We have not discussed the O(n Log
n) solution here as the purpose of this post is to explain Dynamic Programming with a
simple example. See below post for O(n Log n) solution.
Longest Increasing Subsequence Size (N log N)
Source
https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
46
Chapter 4
47
Chapter 4. DP-04 | Longest Common Subsequence
Examples:
1) Consider the input strings “AGGTAB” and “GXTXAYB”. Last characters match for the
strings. So length of LCS can be written as:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)
2) Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match
for the strings. So length of LCS can be written as:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”,
“AEDFH”) )
So the LCS problem has optimal substructure property as the main problem can be solved
using solutions to subproblems.
2) Overlapping Subproblems:
Following is simple recursive implementation of the LCS problem. The implementation
simply follows the recursive structure mentioned above.
C/C++
48
Chapter 4. DP-04 | Longest Common Subsequence
Java
49
Chapter 4. DP-04 | Longest Common Subsequence
char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is" + " " +
lcs.lcs( X, Y, m, n ) );
}
}
// This Code is Contributed by Saket Kumar
Python
C#
50
Chapter 4. DP-04 | Longest Common Subsequence
PHP
<?php
// A Naive recursive PHP
// implementation of LCS problem
function lcs($X, $Y, $m, $n)
{
if($m == 0 || $n == 0)
return 0;
else if ($X[$m - 1] == $Y[$n - 1])
return 1 + lcs($X, $Y,
$m - 1, $n - 1);
else
return max(lcs($X, $Y, $m, $n - 1),
lcs($X, $Y, $m - 1, $n));
}
// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of LCS is ";
51
Chapter 4. DP-04 | Longest Common Subsequence
Output:
Length of LCS is 4
Time complexity of the above naive recursive approach is O(2^n) in worst case and worst
case happens when all characters of X and Y mismatch i.e., length of LCS is 0.
Considering the above implementation, following is a partial recursion tree for input strings
“AXYT” and “AYZX”
lcs("AXYT", "AYZX")
/
lcs("AXY", "AYZX") lcs("AXYT", "AYZ")
/ /
lcs("AX", "AYZX") lcs("AXY", "AYZ") lcs("AXY", "AYZ") lcs("AXYT", "AY")
In the above partial recursion tree, lcs(“AXY”, “AYZ”) is being solved twice. If we draw the
complete recursion tree, then we can see that there are many subproblems which are solved
again and again. So this problem has Overlapping Substructure property and recomputation
of same subproblems can be avoided by either using Memoization or Tabulation. Following
is a tabulated implementation for the LCS problem.
C/C++
52
Chapter 4. DP-04 | Longest Common Subsequence
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Driver program to test above function */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d", lcs( X, Y, m, n ) );
return 0;
}
Java
53
Chapter 4. DP-04 | Longest Common Subsequence
Python
54
Chapter 4. DP-04 | Longest Common Subsequence
# declaring the array for storing the dp values
L = [[None]*(n+1) for i in xrange(m+1)]
"""Following steps build L[m+1][n+1] in bottom up fashion
Note: L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-1]"""
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0 :
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j] , L[i][j-1])
# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
return L[m][n]
#end of function lcs
# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
55
Chapter 4. DP-04 | Longest Common Subsequence
PHP
<?php
// Dynamic Programming C#
// implementation of LCS problem
function lcs($X , $Y)
{
// find the length of the strings
$m = strlen($X);
$n = strlen($Y) ;
// declaring the array for
56
Chapter 4. DP-04 | Longest Common Subsequence
Output:
Length of LCS is 4
Time Complexity of the above implementation is O(mn) which is much better than the
worst-case time complexity of Naive Recursive implementation.
The above algorithm/code returns only length of LCS. Please see the following post for
printing the LCS.
Printing Longest Common Subsequence
57
Chapter 4. DP-04 | Longest Common Subsequence
Source
https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
58
Chapter 5
1. Insert
2. Remove
3. Replace
Examples:
59
Chapter 5. DP-05 | Edit Distance
Let us traverse from right corner, there are two possibilities for every pair of character being
traversed.
1. If last characters of two strings are same, nothing much to do. Ignore last characters
and get count for remaining strings. So we recur for lengths m-1 and n-1.
2. Else (If last characters are not same), we consider all operations on ‘str1’, consider all
three operations on last character of first string, recursively compute minimum cost
for all three operations and take minimum of three values.
(a) Insert: Recur for m and n-1
(b) Remove: Recur for m-1 and n
(c) Replace: Recur for m-1 and n-1
60
Chapter 5. DP-05 | Edit Distance
Java
61
Chapter 5. DP-05 | Edit Distance
Python
62
Chapter 5. DP-05 | Edit Distance
C#
63
Chapter 5. DP-05 | Edit Distance
PHP
<?php
// A Naive recursive Python program
// to find minimum number operations
// to convert str1 to str2
function editDistance($str1, $str2,
$m, $n)
{
// If first string is empty,
// the only option is to insert.
// all characters of second
// string into first
if ($m == 0)
return $n;
// If second string is empty,
// the only option is to
// remove all characters of
// first string
if ($n == 0)
return $m;
// If last characters of two
// strings are same, nothing
// much to do. Ignore last
// characters and get count
// for remaining strings.
if ($str1[$m - 1] == $str2[$n - 1])
{
64
Chapter 5. DP-05 | Edit Distance
Output:
The time complexity of above solution is exponential. In worst case, we may end up doing
O(3m ) operations. The worst case happens when none of characters of two strings match.
Below is a recursive call diagram for worst case.
65
Chapter 5. DP-05 | Edit Distance
We can see that many subproblems are solved, again and again, for example, eD(2,2) is
called three times. Since same suproblems are called again, this problem has Overlapping
Subprolems property. So Edit Distance problem has both properties (see thisand this) of a
dynamic programming problem. Like other typical Dynamic Programming(DP) problems,
recomputations of same subproblems can be avoided by constructing a temporary array that
stores results of subproblems.
C++
66
Chapter 5. DP-05 | Edit Distance
Java
67
Chapter 5. DP-05 | Edit Distance
68
Chapter 5. DP-05 | Edit Distance
}
}/*This code is contributed by Rajat Mishra*/
Python
C#
69
Chapter 5. DP-05 | Edit Distance
70
Chapter 5. DP-05 | Edit Distance
PHP
<?php
// A Dynamic Programming based
// Python program for edit
// distance problem
function editDistDP($str1, $str2,
$m, $n)
{
// Fill d[][] in bottom up manner
for ($i = 0; $i <= $m; $i++)
{
for ($j = 0; $j <= $n; $j++)
{
// If first string is empty,
// only option is to insert
// all characters of second string
if ($i == 0)
$dp[$i][$j] = $j ; // Min. operations = j
// If second string is empty,
// only option is to remove
// all characters of second string
else if($j == 0)
$dp[$i][$j] = $i; // Min. operations = i
71
Chapter 5. DP-05 | Edit Distance
Output:
72
Chapter 5. DP-05 | Edit Distance
Source
https://www.geeksforgeeks.org/edit-distance-dp-5/
73
Chapter 6
The path with minimum cost is highlighted in the following figure. The path is (0, 0) –>
(0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).
74
Chapter 6. DP-06 | Min Cost Path
1) Optimal Substructure
The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or
(m, n-1). So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus
cost[m][n]”.
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]
2) Overlapping Subproblems
Following is simple recursive implementation of the MCP (Minimum Cost Path) problem.
The implementation simply follows the recursive structure mentioned above.
75
Chapter 6. DP-06 | Min Cost Path
{1, 5, 3} };
printf(" %d ", minCost(cost, 2, 2));
return 0;
}
Java
76
Chapter 6. DP-06 | Min Cost Path
// This code is contributed by Sam007
Python3
C#
77
Chapter 6. DP-06 | Min Cost Path
PHP
<?php
/* A Naive recursive implementation
of MCP(Minimum Cost Path) problem */
78
Chapter 6. DP-06 | Min Cost Path
$R = 3;
$C = 3;
/* Returns cost of minimum
cost path from (0,0) to
(m, n) in mat[R][C]*/
function minCost($cost, $m, $n)
{
global $R;
global $C;
if ($n < 0 || $m < 0)
return PHP_INT_MAX;
else if ($m == 0 && $n == 0)
return $cost[$m][$n];
else
return $cost[$m][$n] +
min1(minCost($cost, $m - 1, $n - 1),
minCost($cost, $m - 1, $n),
minCost($cost, $m, $n - 1) );
}
/* A utility function that
returns minimum of 3 integers */
function min1($x, $y, $z)
{
if ($x < $y)
return ($x < $z)? $x : $z;
else
return ($y < $z)? $y : $z;
}
// Driver Code
$cost = array(array(1, 2, 3),
array (4, 8, 2),
array (1, 5, 3));
echo minCost($cost, 2, 2);
// This code is contributed by mits.
?>
Output:
It should be noted that the above function computes the same subproblems again and again.
79
Chapter 6. DP-06 | Min Cost Path
See the following recursion tree, there are many nodes which apear more than once. Time
complexity of this naive recursive solution is exponential and it is terribly slow.
mC refers to minCost()
mC(2, 2)
/ | \
/ | \
mC(1, 1) mC(1, 2) mC(2, 1)
/ | \ / | \ / | \
/ | \ / | \ / | \
mC(0,0) mC(0,1) mC(1,0) mC(0,1) mC(0,2) mC(1,1) mC(1,0) mC(1,1) mC(2,0)
So the MCP problem has both properties (see thisand this) of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, recomputations of same
subproblems can be avoided by constructing a temporary array tc[][] in bottom up manner.
C++
80
Chapter 6. DP-06 | Min Cost Path
Java
81
Chapter 6. DP-06 | Min Cost Path
tc[0][0] = cost[0][0];
/* Initialize first column of total cost(tc) array */
for (i = 1; i <= m; i++)
tc[i][0] = tc[i-1][0] + cost[i][0];
/* Initialize first row of tc array */
for (j = 1; j <= n; j++)
tc[0][j] = tc[0][j-1] + cost[0][j];
/* Construct rest of the tc array */
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tc[i][j] = min(tc[i-1][j-1],
tc[i-1][j],
tc[i][j-1]) + cost[i][j];
return tc[m][n];
}
/* Driver program to test above functions */
public static void main(String args[])
{
int cost[][]= {{1, 2, 3},
{4, 8, 2},
{1, 5, 3}};
System.out.println(minCost(cost,2,2));
}
}
// This code is contributed by Pankaj Kumar
Python
82
Chapter 6. DP-06 | Min Cost Path
# Initialize first column of total cost(tc) array
for i in range(1, m+1):
tc[i][0] = tc[i-1][0] + cost[i][0]
# Initialize first row of tc array
for j in range(1, n+1):
tc[0][j] = tc[0][j-1] + cost[0][j]
# Construct rest of the tc array
for i in range(1, m+1):
for j in range(1, n+1):
tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]
return tc[m][n]
# Driver program to test above functions
cost = [[1, 2, 3],
[4, 8, 2],
[1, 5, 3]]
print(minCost(cost, 2, 2))
# This code is contributed by Bhavya Jain
C#
83
Chapter 6. DP-06 | Min Cost Path
/* Initialize first column of total cost(tc) array */
for (i = 1; i <= m; i++)
tc[i, 0] = tc[i - 1, 0] + cost[i, 0];
/* Initialize first row of tc array */
for (j = 1; j <= n; j++)
tc[0, j] = tc[0, j - 1] + cost[0, j];
/* Construct rest of the tc array */
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tc[i, j] = min(tc[i - 1, j - 1],
tc[i - 1, j],
tc[i, j - 1]) + cost[i, j];
return tc[m, n];
}
// Driver program
public static void Main()
{
int [,]cost= {{1, 2, 3},
{4, 8, 2},
{1, 5, 3}};
Console.Write(minCost(cost,2,2));
}
}
// This code is contributed by Sam007.
PHP
<?php
// DP implementation
// of MCP problem
$R = 3;
$C = 3;
function minCost($cost, $m, $n)
{
global $R;
global $C;
// Instead of following line,
// we can use int tc[m+1][n+1]
// or dynamically allocate
// memory to save space. The
// following line is used to keep
84
Chapter 6. DP-06 | Min Cost Path
Output:
85
Chapter 6. DP-06 | Min Cost Path
Time Complexity of the DP implementation is O(mn) which is much better than Naive
Recursive implementation.
Improved By : Sam007, Mithun Kumar, shiv_bhakt, maveriek
Source
https://www.geeksforgeeks.org/min-cost-path-dp-6/
86
Chapter 7
87
Chapter 7. DP-07 | Coin Change
Java
88
Chapter 7. DP-07 | Coin Change
// If n is less than 0 then no
// solution exists
if (n < 0)
return 0;
// If there are no coins and n
// is greater than 0, then no
// solution exist
if (m <=0 && n >= 1)
return 0;
// count is sum of solutions (i)
// including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) +
count( S, m, n-S[m-1] );
}
// Driver program to test above function
public static void main(String[] args)
{
int i, j;
int arr[] = {1, 2, 3};
int m = arr.length;
System.out.println( count(arr, m, 4));
}
}
// This article is contributed by vt_m.
Python3
89
Chapter 7. DP-07 | Coin Change
C#
90
Chapter 7. DP-07 | Coin Change
// count is sum of solutions (i)
// including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) +
count( S, m, n - S[m - 1] );
}
// Driver program
public static void Main()
{
int []arr = {1, 2, 3};
int m = arr.Length;
Console.Write( count(arr, m, 4));
}
}
// This code is contributed by Sam007
PHP
<?php
// Recursive PHP program for
// coin change problem.
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
function coun($S, $m, $n)
{
// If n is 0 then there is
// 1 solution (do not include
// any coin)
if ($n == 0)
return 1;
// If n is less than 0 then no
// solution exists
if ($n < 0)
return 0;
// If there are no coins and n
// is greater than 0, then no
// solution exist
if ($m <= 0 && $n >= 1)
return 0;
91
Chapter 7. DP-07 | Coin Change
Output :
It should be noted that the above function computes the same subproblems again and again.
See the following recursion tree for S = {1, 2, 3} and n = 5.
The function C({1}, 3) is called two times. If we draw the complete tree, then we can see
that there are many subproblems being called more than once.
Since same suproblems are called again, this problem has Overlapping Subprolems property.
So the Coin Change problem has both properties (see thisand this) of a dynamic program-
ming problem. Like other typical Dynamic Programming(DP) problems, recomputations of
92
Chapter 7. DP-07 | Coin Change
93
Chapter 7. DP-07 | Coin Change
Java
94
Chapter 7. DP-07 | Coin Change
Python
C#
95
Chapter 7. DP-07 | Coin Change
PHP
<?php
// PHP program for
// coin change problem.
function count1($S, $m, $n)
96
Chapter 7. DP-07 | Coin Change
{
// We need n+1 rows as
// the table is constructed
// in bottom up manner
// using the base case 0
// value case (n = 0)
$table;
for ($i = 0; $i < $n + 1; $i++)
for ($j = 0; $j < $m; $j++)
$table[$i][$j] = 0;
// Fill the enteries for
// 0 value case (n = 0)
for ($i = 0; $i < $m; $i++)
$table[0][$i] = 1;
// Fill rest of the table
// entries in bottom up manner
for ($i = 1; $i < $n + 1; $i++)
{
for ($j = 0; $j < $m; $j++)
{
// Count of solutions
// including S[j]
$x = ($i-$S[$j] >= 0) ?
$table[$i - $S[$j]][$j] : 0;
// Count of solutions
// excluding S[j]
$y = ($j >= 1) ?
$table[$i][$j - 1] : 0;
// total count
$table[$i][$j] = $x + $y;
}
}
return $table[$n][$m-1];
}
// Driver Code
$arr = array(1, 2, 3);
$m = count($arr);
$n = 4;
echo count1($arr, $m, $n);
// This code is contributed by mits
?>
97
Chapter 7. DP-07 | Coin Change
Output:
Java
98
Chapter 7. DP-07 | Coin Change
Python
99
Chapter 7. DP-07 | Coin Change
Source
https://www.geeksforgeeks.org/coin-change-dp-7/
100
Chapter 8
However, the order in which we parenthesize the product affects the number of simple arith-
metic operations needed to compute the product, or the efficiency. For example, suppose A
is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
101
Chapter 8. DP-08 | Matrix Chain Multiplication
1) Optimal Substructure:
A simple solution is to place parenthesis at all possible places, calculate the cost for each
placement and return the minimum value. In a chain of matrices of size n, we can place
the first set of parenthesis in n-1 ways. For example, if the given chain is of 4 matrices.
let the chain be ABCD, then there are 3 ways to place first set of parenthesis outer side:
(A)(BCD), (AB)(CD) and (ABC)(D). So when we place a set of parenthesis, we divide the
problem into subproblems of smaller size. Therefore, the problem has optimal substructure
property and can be easily solved using recursion.
Minimum number of multiplication needed to multiply a chain of size n = Minimum of all
n-1 placements (these placements create subproblems of smaller size)
2) Overlapping Subproblems
Following is a recursive implementation that simply follows the above optimal substructure
property.
102
Chapter 8. DP-08 | Matrix Chain Multiplication
Java
103
Chapter 8. DP-08 | Matrix Chain Multiplication
Python3
104
Chapter 8. DP-08 | Matrix Chain Multiplication
C#
105
Chapter 8. DP-08 | Matrix Chain Multiplication
Time complexity of the above naive recursive approach is exponential. It should be noted
that the above function computes the same subproblems again and again. See the following
recursion tree for a matrix chain of size 4. The function MatrixChainOrder(p, 3, 4) is called
two times. We can see that there are many subproblems being called more than once.
106
Chapter 8. DP-08 | Matrix Chain Multiplication
Since same suproblems are called again, this problem has Overlapping Subprolems property.
So Matrix Chain Multiplication problem has both properties (see thisand this) of a dynamic
programming problem. Like other typical Dynamic Programming(DP) problems, recompu-
tations of same subproblems can be avoided by constructing a temporary array m[][] in
bottom up manner.
Dynamic Programming Solution
Following is C/C++ implementation for Matrix Chain Multiplication problem using
Dynamic Programming.
107
Chapter 8. DP-08 | Matrix Chain Multiplication
}
}
}
return m[1][n-1];
}
int main()
{
int arr[] = {1, 2, 3, 4};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, size));
getchar();
return 0;
}
Java
108
Chapter 8. DP-08 | Matrix Chain Multiplication
{
j = i+L-1;
if(j == n) continue;
m[i][j] = Integer.MAX_VALUE;
for (k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n-1];
}
// Driver program to test above function
public static void main(String args[])
{
int arr[] = new int[] {1, 2, 3, 4};
int size = arr.length;
System.out.println("Minimum number of multiplications is "+
MatrixChainOrder(arr, size));
}
}
/* This code is contributed by Rajat Mishra*/
Python
109
Chapter 8. DP-08 | Matrix Chain Multiplication
C#
110
Chapter 8. DP-08 | Matrix Chain Multiplication
/* m[i,j] = Minimum number of scalar
multiplications needed
to compute the matrix A[i]A[i+1]...A[j]
= A[i..j] where dimension of A[i] is
p[i-1] x p[i] */
// cost is zero when multiplying
// one matrix.
for (i = 1; i < n; i++)
m[i, i] = 0;
// L is chain length.
for (L = 2; L < n; L++)
{
for (i = 1; i < n-L+1; i++)
{
j = i+L-1;
if(j == n) continue;
m[i, j] = int.MaxValue;
for (k = i; k <= j-1; k++)
{
// q = cost/scalar multiplications
q = m[i, k] + m[k+1, j] +
p[i-1]*p[k]*p[j];
if (q < m[i, j])
m[i, j] = q;
}
}
}
return m[1, n-1];
}
// Driver program to test above function
public static void Main()
{
int []arr = new int[] {1, 2, 3, 4};
int size = arr.Length;
Console.Write("Minimum number of " +
"multiplications is "+
MatrixChainOrder(arr, size));
}
}
// This code is contributed by Sam007
111
Chapter 8. DP-08 | Matrix Chain Multiplication
Output:
Source
https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
112
Chapter 9
1. A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion
of (1 + X)^n.
2. A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that
k objects can be chosen from among n objects; more formally, the number of k-element
subsets (or k-combinations) of an n-element set.
The Problem
Write a function that takes two parameters n and k and returns the value of Binomial
Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it
should return 10 for n = 5 and k = 2.
1) Optimal Substructure
The value of C(n, k) can be recursively calculated using following standard formula for
Binomial Coefficients.
Following is a simple recursive implementation that simply follows the recursive structure
mentioned above.
C/C++
113
Chapter 9. DP-09 | Binomial Coefficient
{
// Base Cases
if (k==0 || k==n)
return 1;
// Recur
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
/* Driver program to test above function*/
int main()
{
int n = 5, k = 2;
printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
return 0;
}
Java
114
Chapter 9. DP-09 | Binomial Coefficient
Python
C#
115
Chapter 9. DP-09 | Binomial Coefficient
PHP
<?php
// PHP Code for Dynamic Programming |
// Set 9 (Binomial Coefficient)
// Returns value of
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{
// Base Cases
if ($k==0 || $k==$n)
return 1;
// Recur
return binomialCoeff($n - 1, $k - 1) +
binomialCoeff($n - 1, $k);
}
// Driver Code
$n = 5;
$k = 2;
echo "Value of C","(",$n ,$k,") is "
, binomialCoeff($n, $k);
// This code is contributed by aj_36
?>
Output:
Value of C(52) is 10
2) Overlapping Subproblems
It should be noted that the above function computes the same subproblems again and again.
See the following recursion tree for n = 5 an k = 2. The function C(3, 1) is called two times.
For large values of n, there will be many common subproblems.
C(5, 2)
116
Chapter 9. DP-09 | Binomial Coefficient
/ \
C(4, 1) C(4, 2)
/ \ / \
C(3, 0) C(3, 1) C(3, 1) C(3, 2)
/ \ / \ / \
C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2)
/ \ / \ / \
C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)
Since same suproblems are called again, this problem has Overlapping Subproblems prop-
erty. So the Binomial Coefficient problem has both properties (see thisand this) of a dy-
namic programming problem. Like other typical Dynamic Programming(DP) problems,
re-computations of same subproblems can be avoided by constructing a temporary array
C[][] in bottom up manner. Following is Dynamic Programming based implementation.
C
117
Chapter 9. DP-09 | Binomial Coefficient
Java
118
Chapter 9. DP-09 | Binomial Coefficient
Python
C#
119
Chapter 9. DP-09 | Binomial Coefficient
using System;
class GFG {
// Returns value of Binomial Coefficient
// C(n, k)
static int binomialCoeff(int n, int k)
{
int [,]C = new int[n+1,k+1];
int i, j;
// Calculate value of Binomial
// Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= Math.Min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i,j] = 1;
// Calculate value using previosly
// stored values
else
C[i,j] = C[i-1,j-1] + C[i-1,j];
}
}
return C[n,k];
}
// A utility function to return minimum
// of two integers
static int min(int a, int b)
{
return (a < b) ? a : b;
}
/* Driver program to test above function*/
public static void Main()
{
int n = 5, k = 2;
Console.WriteLine("Value of C(" + n
+ "," + k + ") is "
+ binomialCoeff(n, k));
}
}
120
Chapter 9. DP-09 | Binomial Coefficient
PHP
<?php
// A Dynamic Programming based
// solution that uses table C[][] to
// calculate the Binomial Coefficient
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff( $n, $k)
{
$C = array(array());
$i; $j;
// Caculate value of Binomial
// Coefficient in bottom up manner
for ($i = 0; $i <= $n; $i++)
{
for ($j = 0; $j <= min($i, $k); $j++)
{
// Base Cases
if ($j == 0 || $j == $i)
$C[$i][$j] = 1;
// Calculate value using
// previosly stored values
else
$C[$i][$j] = $C[$i - 1][$j - 1] +
$C[$i - 1][$j];
}
}
return $C[$n][$k];
}
// Driver Code
$n = 5;
$k = 2;
echo "Value of C(" ,$n," ",$k, ") is"," "
, binomialCoeff($n, $k) ;
// This code is contributed by anuj_67.
?>
Output:
121
Chapter 9. DP-09 | Binomial Coefficient
Value of C[5][2] is 10
C/C++
Java
122
Chapter 9. DP-09 | Binomial Coefficient
class GFG {
static int binomialCoeff(int n, int k)
{
int C[] = new int[k + 1];
// nC0 is 1
C[0] = 1;
for (int i = 1; i <= n; i++)
{
// Compute next row of pascal
// triangle using the previous row
for (int j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j-1];
}
return C[k];
}
/* Driver program */
public static void main(String[] args)
{
int n = 5, k = 2;
System.out.printf("Value of C(%d, %d) is %d "
, n, k, binomialCoeff(n, k));
}
}
Python
123
Chapter 9. DP-09 | Binomial Coefficient
return C[k]
# Driver Program to test the above function
n = 5
k = 2
print "Value of C(%d,%d) is %d" %(n,k,binomialCoeff(n,k))
# This code is contribtued by Nikhil Kumar Singh(nickzuck_007)
C#
124
Chapter 9. DP-09 | Binomial Coefficient
PHP
<?php
// PHP program for space optimized
// Dynamic Programming Solution of
// Binomial Coefficient
function binomialCoeff($n, $k)
{
$C = array_fill(0, $k + 1, 0);
$C[0] = 1; // nC0 is 1
for ($i = 1; $i <= $n; $i++)
{
// Compute next row of pascal
// triangle using the previous row
for ($j = min($i, $k); $j > 0; $j--)
$C[$j] = $C[$j] + $C[$j - 1];
}
return $C[$k];
}
// Driver Code
$n = 5; $k = 2;
echo "Value of C[$n, $k] is ".
binomialCoeff($n, $k);
// This code is contributed by mits.
?>
Output:
Value of C[5][2] is 10
125
Chapter 9. DP-09 | Binomial Coefficient
For i = 1:
C[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1
For i = 2:
C[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1
C[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,2) = 2
For i=3:
C[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1
C[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3
C[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3
For i=4:
C[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1
C[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4
C[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6
C[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4
Source
https://www.geeksforgeeks.org/binomial-coefficient-dp-9/
126
Chapter 10
A simple solution is to consider all subsets of items and calculate the total weight and value
of all subsets. Consider the only subsets whose total weight is smaller than W. From all
such subsets, pick the maximum value subset.
1) Optimal Substructure:
To consider all subsets of items, there can be two cases for every item: (1) the item is
included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two
values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
127
Chapter 10. DP-10 | 0-1 Knapsack Problem
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the
nth item (including nth item).
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is
the only possibility.
2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned
above.
C/C++
128
Chapter 10. DP-10 | 0-1 Knapsack Problem
Java
Python
129
Chapter 10. DP-10 | 0-1 Knapsack Problem
# capacity W
def knapSack(W , wt , val , n):
# Base Case
if n == 0 or W == 0 :
return 0
# If weight of the nth item is more than Knapsack of capacity
# W, then this item cannot be included in the optimal solution
if (wt[n-1] > W):
return knapSack(W , wt , val , n-1)
# return the maximum of two cases:
# (1) nth item included
# (2) not included
else:
return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),
knapSack(W , wt , val , n-1))
# end of function knapSack
# To test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print knapSack(W , wt , val , n)
# This code is contributed by Nikhil Kumar Singh
C#
130
Chapter 10. DP-10 | 0-1 Knapsack Problem
PHP
<?php
// A Naive recursive implementation
// of 0-1 Knapsack problem
// Returns the maximum value that
// can be put in a knapsack of
// capacity W
function knapSack($W, $wt, $val, $n)
{
// Base Case
131
Chapter 10. DP-10 | 0-1 Knapsack Problem
if ($n == 0 || $W == 0)
return 0;
// If weight of the nth item is
// more than Knapsack capacity
// W, then this item cannot be
// included in the optimal solution
if ($wt[$n - 1] > $W)
return knapSack($W, $wt, $val, $n - 1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return max($val[$n - 1] +
knapSack($W - $wt[$n - 1],
$wt, $val, $n - 1),
knapSack($W, $wt, $val, $n-1));
}
// Driver Code
$val = array(60, 100, 120);
$wt = array(10, 20, 30);
$W = 50;
$n = count($val);
echo knapSack($W, $wt, $val, $n);
// This code is contributed by Sam007
?>
Output:
220
It should be noted that the above function computes the same subproblems again and again.
See the following recursion tree, K(1, 1) is being evaluated twice. Time complexity of this
naive recursive solution is exponential (2^n).
132
Chapter 10. DP-10 | 0-1 Knapsack Problem
/ \ / \
/ \ / \
K(1,2) K(1,1) K(1,1) K(1,0)
/ \ / \ / \
/ \ / \ / \
K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0)
Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.
Since suproblems are evaluated again, this problem has Overlapping Subprolems property.
So the 0-1 Knapsack problem has both properties (see thisand this) of a dynamic program-
ming problem. Like other typical Dynamic Programming(DP) problems, recomputations
of same subproblems can be avoided by constructing a temporary array K[][] in bottom up
manner. Following is Dynamic Programming based implementation.
C++
133
Chapter 10. DP-10 | 0-1 Knapsack Problem
Java
134
Chapter 10. DP-10 | 0-1 Knapsack Problem
}
}
/*This code is contributed by Rajat Mishra */
Python
C#
135
Chapter 10. DP-10 | 0-1 Knapsack Problem
PHP
<?php
// A Dynamic Programming based solution
136
Chapter 10. DP-10 | 0-1 Knapsack Problem
Output:
220
Time Complexity: O(nW) where n is the number of items and W is the capacity of knapsack.
References:
http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
137
Chapter 10. DP-10 | 0-1 Knapsack Problem
http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.
pdf
Improved By : Sam007
Source
https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
138
Chapter 11
139
Chapter 11. DP-11 | Egg Dropping Puzzle
1) If the egg breaks after dropping from xth floor, then we only need to check for floors
lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for
floors higher than x; so the problem reduces to k-x floors and n eggs.
Since we need to minimize the number of trials in worst case, we take the maximum of two
cases. We consider the max of above two cases for every floor and choose the floor which
yields minimum number of trials.
2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned
above.
C
# include <stdio.h>
# include <limits.h>
// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b)? a: b; }
/* Function to get minimum number of trials needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
// If there are no floors, then no trials needed. OR if there is
// one floor, one trial needed.
if (k == 1 || k == 0)
return k;
// We need k trials for one egg and k floors
if (n == 1)
return k;
int min = INT_MAX, x, res;
// Consider all droppings from 1st floor to kth floor and
// return the minimum of these values plus 1.
for (x = 1; x <= k; x++)
{
140
Chapter 11. DP-11 | Egg Dropping Puzzle
C#
using System;
class GFG {
/* Function to get minimum number of
trials needed in worst case with n
eggs and k floors */
static int eggDrop(int n, int k)
{
// If there are no floors, then
// no trials needed. OR if there
// is one floor, one trial needed.
if (k == 1 || k == 0)
return k;
// We need k trials for one egg
// and k floors
if (n == 1)
return k;
int min = int.MaxValue;
int x, res;
// Consider all droppings from
//1st floor to kth floor and
// return the minimum of these
// values plus 1.
for (x = 1; x <= k; x++)
{
141
Chapter 11. DP-11 | Egg Dropping Puzzle
Output:
Minimum number of trials in worst case with 2 eggs and 10 floors is 4
It should be noted that the above function computes the same subproblems again and again.
See the following partial recursion tree, E(2, 2) is being evaluated twice. There will many
repeated subproblems when you draw the complete recursion tree even for small values of
n and k.
E(2,4)
|
-------------------------------------
| | | |
| | | |
x=1/ x=2/ x=3/ x=4/
/ / .... ....
/ /
E(1,0) E(2,3) E(1,1) E(2,2)
/ /... /
x=1/ .....
/
E(1,0) E(2,2)
/
142
Chapter 11. DP-11 | Egg Dropping Puzzle
......
Since same suproblems are called again, this problem has Overlapping Subprolems property.
So Egg Dropping Puzzle has both properties (see thisand this) of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, recomputations of same
subproblems can be avoided by constructing a temporary array eggFloor[][] in bottom up
manner.
Dynamic Programming Solution
Following are the implementations for Egg Dropping problem using Dynamic Programming.
C++
// A Dynamic Programming based C++ Program for the Egg Dropping Puzzle
# include <stdio.h>
# include <limits.h>
// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b)? a: b; }
/* Function to get minimum number of trials needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
/* A 2D table where entery eggFloor[i][j] will represent minimum
number of trials needed for i eggs and j floors. */
int eggFloor[n+1][k+1];
int res;
int i, j, x;
// We need one trial for one floor and0 trials for 0 floors
for (i = 1; i <= n; i++)
{
eggFloor[i][1] = 1;
eggFloor[i][0] = 0;
}
// We always need j trials for one egg and j floors.
for (j = 1; j <= k; j++)
eggFloor[1][j] = j;
// Fill rest of the entries in table using optimal substructure
// property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
143
Chapter 11. DP-11 | Egg Dropping Puzzle
{
eggFloor[i][j] = INT_MAX;
for (x = 1; x <= j; x++)
{
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
if (res < eggFloor[i][j])
eggFloor[i][j] = res;
}
}
}
// eggFloor[n][k] holds the result
return eggFloor[n][k];
}
/* Driver program to test to pront printDups*/
int main()
{
int n = 2, k = 36;
printf ("nMinimum number of trials in worst case with %d eggs and "
"%d floors is %d \n", n, k, eggDrop(n, k));
return 0;
}
Java
//A Dynamic Programming based Python Program for the Egg Dropping Puzzle
class EggDrop
{
// A utility function to get maximum of two integers
static int max(int a, int b) { return (a > b)? a: b; }
/* Function to get minimum number of trials needed in worst
case with n eggs and k floors */
static int eggDrop(int n, int k)
{
/* A 2D table where entery eggFloor[i][j] will represent minimum
number of trials needed for i eggs and j floors. */
int eggFloor[][] = new int[n+1][k+1];
int res;
int i, j, x;
// We need one trial for one floor and0 trials for 0 floors
for (i = 1; i <= n; i++)
{
eggFloor[i][1] = 1;
eggFloor[i][0] = 0;
}
144
Chapter 11. DP-11 | Egg Dropping Puzzle
// We always need j trials for one egg and j floors.
for (j = 1; j <= k; j++)
eggFloor[1][j] = j;
// Fill rest of the entries in table using optimal substructure
// property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
{
eggFloor[i][j] = Integer.MAX_VALUE;
for (x = 1; x <= j; x++)
{
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
if (res < eggFloor[i][j])
eggFloor[i][j] = res;
}
}
}
// eggFloor[n][k] holds the result
return eggFloor[n][k];
}
/* Driver program to test to pront printDups*/
public static void main(String args[] )
{
int n = 2, k = 10;
System.out.println("Minimum number of trials in worst case with "+n+" eggs and "+k+
" floors is "+eggDrop(n, k));
}
}
/*This code is contributed by Rajat Mishra*/
Python
# A Dynamic Programming based Python Program for the Egg Dropping Puzzle
INT_MAX = 32767
# Function to get minimum number of trials needed in worst
# case with n eggs and k floors
def eggDrop(n, k):
# A 2D table where entery eggFloor[i][j] will represent minimum
# number of trials needed for i eggs and j floors.
eggFloor = [[0 for x in range(k+1)] for x in range(n+1)]
145
Chapter 11. DP-11 | Egg Dropping Puzzle
# We need one trial for one floor and0 trials for 0 floors
for i in range(1, n+1):
eggFloor[i][1] = 1
eggFloor[i][0] = 0
# We always need j trials for one egg and j floors.
for j in range(1, k+1):
eggFloor[1][j] = j
# Fill rest of the entries in table using optimal substructure
# property
for i in range(2, n+1):
for j in range(2, k+1):
eggFloor[i][j] = INT_MAX
for x in range(1, j+1):
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
if res < eggFloor[i][j]:
eggFloor[i][j] = res
# eggFloor[n][k] holds the result
return eggFloor[n][k]
# Driver program to test to pront printDups
n = 2
k = 36
print("Minimum number of trials in worst case with" + str(n) + "eggs and "
+ str(k) + " floors is " + str(eggDrop(n, k)))
# This code is contributed by Bhavya Jain
C#
146
Chapter 11. DP-11 | Egg Dropping Puzzle
147
Chapter 11. DP-11 | Egg Dropping Puzzle
int n = 2, k = 36;
Console.WriteLine("Minimum number of trials "
+ "in worst case with " + n + " eggs and "
+ k + "floors is " + eggDrop(n, k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A Dynamic Programming based PHP
// Program for the Egg Dropping Puzzle
/* Function to get minimum number
of trials needed in worst
case with n eggs and k floors */
function eggDrop($n, $k)
{
/* A 2D table where entery eggFloor[i][j]
will represent minimum number of
trials needed for i eggs and j floors. */
$eggFloor = array(array());;
// We need one trial for one
// floor and0 trials for 0 floors
for ($i = 1; $i <=$n;$i++)
{
$eggFloor[$i][1] = 1;
$eggFloor[$i][0] = 0;
}
// We always need j trials
// for one egg and j floors.
for ($j = 1; $j <= $k; $j++)
$eggFloor[1][$j] = $j;
// Fill rest of the entries in
// table using optimal substructure
// property
for ($i = 2; $i <= $n; $i++)
{
for ($j = 2; $j <= $k; $j++)
{
$eggFloor[$i][$j] = 999999;
for ($x = 1; $x <= $j; $x++)
148
Chapter 11. DP-11 | Egg Dropping Puzzle
{
$res = 1 + max($eggFloor[$i - 1][$x - 1],
$eggFloor[$i][$j - $x]);
if ($res < $eggFloor[$i][$j])
$eggFloor[$i][$j] = $res;
}
}
}
// eggFloor[n][k] holds the result
return $eggFloor[$n][$k];
}
// Driver Code
$n = 2;
$k = 36;
echo "Minimum number of trials in worst case with " .$n. " eggs and "
.$k. " floors is " .eggDrop($n, $k) ;
// This code is contributed by Sam007
?>
Output :
Source
https://www.geeksforgeeks.org/egg-dropping-puzzle-dp-11/
149
Chapter 12
As another example, if the given sequence is “BBABCBCAB”, then the output should be 7
as “BABCBAB” is the longest palindromic subseuqnce in it. “BBBBB” and “BBCBB” are
also palindromic subsequences of the given sequence, but not the longest ones.
The naive solution for this problem is to generate all subsequences of the given sequence
and find the longest palindromic subsequence. This solution is exponential in term of time
complexity. Let us see how this problem possesses both important properties of a Dynamic
Programming (DP) Problem and can efficiently solved using Dynamic Programming.
1) Optimal Substructure:
Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest
palindromic subsequence of X[0..n-1].
If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).
Following is a general recursive solution with all cases handled.
150
Chapter 12. DP-12 | Longest Palindromic Subsequence
// If there are more than two characters, and first and last
// characters are same
Else L(i, j) = L(i + 1, j - 1) + 2
2) Overlapping Subproblems
Following is simple recursive implementation of the LPS problem. The implementation
simply follows the recursive structure mentioned above.
#include<stdio.h>
#include<string.h>
// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest palindromic subsequence in seq
int lps(char *seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j)
return 1;
// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
// If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKSFORGEEKS";
int n = strlen(seq);
printf ("The length of the LPS is %d", lps(seq, 0, n-1));
151
Chapter 12. DP-12 | Longest Palindromic Subsequence
getchar();
return 0;
}
Output:
Considering the above implementation, following is a partial recursion tree for a sequence
of length 6 with all different characters.
L(0, 5)
/ \
/ \
L(1,5) L(0,4)
/ \ / \
/ \ / \
L(2,5) L(1,4) L(1,4) L(0,3)
In the above partial recursion tree, L(1, 4) is being solved twice. If we draw the complete
recursion tree, then we can see that there are many subproblems which are solved again and
again. Since same suproblems are called again, this problem has Overlapping Subprolems
property. So LPS problem has both properties (see thisand this) of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, recomputations of same
subproblems can be avoided by constructing a temporary array L[][] in bottom up manner.
Dynamic Programming Solution
C++
152
Chapter 12. DP-12 | Longest Palindromic Subsequence
// Strings of length 1 are palindrome of lentgh 1
for (i = 0; i < n; i++)
L[i][i] = 1;
// Build the table. Note that the lower diagonal values of table are
// useless and not filled in the process. The values are filled in a
// manner similar to Matrix Chain Multiplication DP solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/). cl is length of
// substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKS FOR GEEKS";
int n = strlen(seq);
printf ("The lnegth of the LPS is %d", lps(seq));
getchar();
return 0;
}
Java
//A Dynamic Programming based Python Program for the Egg Dropping Puzzle
class LPS
{
// A utility function to get max of two integers
static int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest palindromic subsequence in seq
153
Chapter 12. DP-12 | Longest Palindromic Subsequence
Python
154
Chapter 12. DP-12 | Longest Palindromic Subsequence
# Create a table to store results of subproblems
L = [[0 for x in range(n)] for x in range(n)]
# Strings of length 1 are palindrome of length 1
for i in range(n):
L[i][i] = 1
# Build the table. Note that the lower diagonal values of table are
# useless and not filled in the process. The values are filled in a
# manner similar to Matrix Chain Multiplication DP solution (See
# https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
# cl is length of substring
for cl in range(2, n+1):
for i in range(n-cl+1):
j = i+cl-1
if str[i] == str[j] and cl == 2:
L[i][j] = 2
elif str[i] == str[j]:
L[i][j] = L[i+1][j-1] + 2
else:
L[i][j] = max(L[i][j-1], L[i+1][j]);
return L[0][n-1]
# Driver program to test above functions
seq = "GEEKS FOR GEEKS"
n = len(seq)
print("The length of the LPS is " + str(lps(seq)))
# This code is contributed by Bhavya Jain
C#
155
Chapter 12. DP-12 | Longest Palindromic Subsequence
156
Chapter 12. DP-12 | Longest Palindromic Subsequence
PHP
<?php
// A Dynamic Programming based
// PHP program for LPS problem
// Returns the length of the
// longest palindromic
// subsequence in seq
// A utility function to get
// max of two integers
// function max( $x, $y)
// { return ($x > $y)? $x : $y; }
// Returns the length of the
// longest palindromic
// subsequence in seq
function lps($str)
{
$n = strlen($str);
$i; $j; $cl;
// Create a table to store
// results of subproblems
$L[][] = array(array());
// Strings of length 1 are
// palindrome of lentgh 1
for ($i = 0; $i < $n; $i++)
$L[$i][$i] = 1;
// Build the table. Note that
// the lower diagonal values
// of table are useless and
// not filled in the process.
// The values are filled in a
// manner similar to Matrix
// Chain Multiplication DP
157
Chapter 12. DP-12 | Longest Palindromic Subsequence
Output:
Time Complexity of the above implementation is O(n^2) which is much better than the
worst case time complexity of Naive Recursive implementation.
This problem is close to the Longest Common Subsequence (LCS) problem. In fact, we can
use LCS as a subroutine to solve this problem. Following is the two step solution that uses
LCS.
1) Reverse the given sequence and store the reverse in another array say rev[0..n-1]
2) LCS of the given sequence and rev[] will be the longest palindromic sequence.
This solution is also a O(n^2) solution.
158
Chapter 12. DP-12 | Longest Palindromic Subsequence
References:
http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf
Improved By : nitin mittal, shiv_bhakt
Source
https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
159
Chapter 13
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20
And if the prices are as following, then the maximum obtainable value is 24 (by cutting in
eight pieces of length 1)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20
A naive solution for this problem is to generate all configurations of different pieces and find
the highest priced configuration. This solution is exponential in term of time complexity.
Let us see how this problem possesses both important properties of a Dynamic Programming
(DP) Problem and can efficiently solved using Dynamic Programming.
1) Optimal Substructure:
We can get the best price by making a cut at different positions and comparing the values
obtained after a cut. We can recursively call the same function for a piece obtained after a
cut.
160
Chapter 13. DP-13 | Cutting a Rod
Let cutRod(n) be the required (best possible price) value for a rod of length n. cutRod(n)
can be written as following.
cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}
2) Overlapping Subproblems
Following is simple recursive implementation of the Rod Cutting problem. The implemen-
tation simply follows the recursive structure mentioned above.
C++
Java
161
Chapter 13. DP-13 | Cutting a Rod
{
/* Returns the best obtainable price for a rod of length
n and price[] as prices of different pieces */
static int cutRod(int price[], int n)
{
if (n <= 0)
return 0;
int max_val = Integer.MIN_VALUE;
// Recursively cut the rod in different pieces and
// compare different configurations
for (int i = 0; i<n; i++)
max_val = Math.max(max_val,
price[i] + cutRod(price, n-i-1));
return max_val;
}
/* Driver program to test above functions */
public static void main(String args[])
{
int arr[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
int size = arr.length;
System.out.println("Maximum Obtainable Value is "+
cutRod(arr, size));
}
}
/* This code is contributed by Rajat Mishra */
Python
162
Chapter 13. DP-13 | Cutting a Rod
C#
163
Chapter 13. DP-13 | Cutting a Rod
}
}
// This code is contributed by Sam007
PHP
<?php
// A Naive recursive solution for
// Rod cutting problem
/* Returns the best obtainable
price for a rod of length n and
price[] as prices of different
pieces */
function cutRod( $price, $n)
{
if ($n <= 0)
return 0;
$max_val = PHP_INT_MIN;
// Recursively cut the rod in different
// pieces and compare different
// configurations
for ($i = 0; $i < $n; $i++)
$max_val = max($max_val, $price[$i] +
cutRod($price, $n - $i - 1));
return $max_val;
}
// Driver Code
$arr = array(1, 5, 8, 9, 10, 17, 17, 20);
$size =count($arr);
echo "Maximum Obtainable Value is "
, cutRod($arr, $size);
// This code is contributed anuj_67.
?>
Output:
Considering the above implementation, following is recursion tree for a Rod of length 4.
164
Chapter 13. DP-13 | Cutting a Rod
cR(4)
/ /
/ /
cR(3) cR(2) cR(1) cR(0)
/ | / |
/ | / |
cR(2) cR(1) cR(0) cR(1) cR(0) cR(0)
/ | |
/ | |
cR(1) cR(0) cR(0) cR(0)
/
/
CR(0)
In the above partial recursion tree, cR(2) is being solved twice. We can see that there are
many subproblems which are solved again and again. Since same suproblems are called
again, this problem has Overlapping Subprolems property. So the Rod Cutting problem has
both properties (see thisand this) of a dynamic programming problem. Like other typical
Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided
by constructing a temporary array val[] in bottom up manner.
C++
165
Chapter 13. DP-13 | Cutting a Rod
val[i] = max_val;
}
return val[n];
}
/* Driver program to test above functions */
int main()
{
int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum Obtainable Value is %dn", cutRod(arr, size));
getchar();
return 0;
}
Java
166
Chapter 13. DP-13 | Cutting a Rod
cutRod(arr, size));
}
}
/* This code is contributed by Rajat Mishra */
Python
C#
167
Chapter 13. DP-13 | Cutting a Rod
val[0] = 0;
// Build the table val[] in
// bottom up manner and return
// the last entry from the table
for (int i = 1; i<=n; i++)
{
int max_val = int.MinValue;
for (int j = 0; j < i; j++)
max_val = Math.Max(max_val,
price[j] + val[i - j - 1]);
val[i] = max_val;
}
return val[n];
}
// Driver Code
public static void Main()
{
int []arr = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
int size = arr.Length;
Console.WriteLine("Maximum Obtainable Value is " +
cutRod(arr, size));
}
}
// This code is contributed by Sam007
PHP
<?php
// A Dynamic Programming solution for
// Rod cutting problem
/* Returns the best obtainable price
for a rod of length n and price[] as
prices of different pieces */
function cutRod( $price, $n)
{
$val = array();
$val[0] = 0;
$i; $j;
// Build the table val[] in bottom
// up manner and return the last
// entry from the table
168
Chapter 13. DP-13 | Cutting a Rod
Output:
Time Complexity of the above implementation is O(n^2) which is much better than the
worst-case time complexity of Naive Recursive implementation.
Improved By : Sam007, vt_m, aniketmaurya
Source
https://www.geeksforgeeks.org/cutting-a-rod-dp-13/
169
Chapter 14
Solution
This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. We
need a slight change in the Dynamic Programming solution of LIS problem. All we need to
change is to use sum as a criteria instead of length of increasing subsequence.
Following are the Dynamic Programming solution to the problem :
C/C++
170
Chapter 14. DP-14 | Maximum Sum Increasing Subsequence
Java
171
Chapter 14. DP-14 | Maximum Sum Increasing Subsequence
/* Initialize msis values
for all indexes */
for (i = 0; i < n; i++)
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of all
msis values */
for (i = 0; i < n; i++)
if (max < msis[i])
max = msis[i];
return max;
}
// Driver code
public static void main(String args[])
{
int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};
int n = arr.length;
System.out.println("Sum of maximum sum "+
"increasing subsequence is "+
maxSumIS(arr, n));
}
}
// This code is contributed
// by Rajat Mishra
Python
172
Chapter 14. DP-14 | Maximum Sum Increasing Subsequence
max = 0
msis = [0 for x in range(n)]
# Initialize msis values
# for all indexes
for i in range(n):
msis[i] = arr[i]
# Compute maximum sum
# values in bottom up manner
for i in range(1, n):
for j in range(i):
if (arr[i] > arr[j] and
msis[i] < msis[j] + arr[i]):
msis[i] = msis[j] + arr[i]
# Pick maximum of
# all msis values
for i in range(n):
if max < msis[i]:
max = msis[i]
return max
# Driver Code
arr = [1, 101, 2, 3, 100, 4, 5]
n = len(arr)
print("Sum of maximum sum increasing " +
"subsequence is " +
str(maxSumIS(arr, n)))
# This code is contributed
# by Bhavya Jain
C#
173
Chapter 14. DP-14 | Maximum Sum Increasing Subsequence
PHP
<?php
// Dynamic Programming implementation
// of Maximum Sum Increasing
// Subsequence (MSIS) problem
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
function maxSumIS($arr, $n)
174
Chapter 14. DP-14 | Maximum Sum Increasing Subsequence
{
$max = 0;
$msis= array($n);
// Initialize msis values
// for all indexes
for($i = 0; $i < $n; $i++ )
$msis[$i] = $arr[$i];
// Compute maximum sum values
// in bottom up manner
for($i = 1; $i < $n; $i++)
for($j = 0; $j < $i; $j++)
if ($arr[$i] > $arr[$j] &&
$msis[$i] < $msis[$j] + $arr[$i])
$msis[$i] = $msis[$j] + $arr[$i];
// Pick maximum of all msis values
for($i = 0;$i < $n; $i++ )
if ($max < $msis[$i] )
$max = $msis[$i];
return $max;
}
// Driver Code
$arr = array(1, 101, 2, 3, 100, 4, 5);
$n = count($arr);
echo "Sum of maximum sum increasing subsequence is "
.maxSumIS( $arr, $n );
// This code is contributed by Sam007
?>
Output :
175
Chapter 14. DP-14 | Maximum Sum Increasing Subsequence
Source
https://www.geeksforgeeks.org/maximum-sum-increasing-subsequence-dp-14/
176
Chapter 15
177
Chapter 15. DP-15 | Longest Bitonic Subsequence
C++
178
Chapter 15. DP-15 | Longest Bitonic Subsequence
Java
179
Chapter 15. DP-15 | Longest Bitonic Subsequence
all indexes */
int[] lds = new int [n];
for (i = 0; i < n; i++)
lds[i] = 1;
/* Compute LDS values from right to left */
for (i = n-2; i >= 0; i--)
for (j = n-1; j > i; j--)
if (arr[i] > arr[j] && lds[i] < lds[j] + 1)
lds[i] = lds[j] + 1;
/* Return the maximum value of lis[i] + lds[i] - 1*/
int max = lis[0] + lds[0] - 1;
for (i = 1; i < n; i++)
if (lis[i] + lds[i] - 1 > max)
max = lis[i] + lds[i] - 1;
return max;
}
public static void main (String[] args)
{
int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
13, 3, 11, 7, 15};
int n = arr.length;
System.out.println("Length of LBS is "+ lbs( arr, n ));
}
}
Python
180
Chapter 15. DP-15 | Longest Bitonic Subsequence
C#
181
Chapter 15. DP-15 | Longest Bitonic Subsequence
182
Chapter 15. DP-15 | Longest Bitonic Subsequence
Output:
Length of LBS is 7
Source
https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/
183
Chapter 16
Input:
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0} }
which represents the following graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3
Note that the value of graph[i][j] is 0 if i is equal to j
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.
Output:
Shortest distance matrix
0 5 8 9
INF 0 3 4
184
Chapter 16. DP-16 | Floyd Warshall Algorithm
INF INF 0 1
INF INF INF 0
C/C++
185
Chapter 16. DP-16 | Floyd Warshall Algorithm
/* Initialize the solution matrix same as input graph matrix. Or
we can say the initial values of shortest distances are based
on shortest paths considering no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to the set of intermediate vertices.
---> Before start of an iteration, we have shortest distances between all
pairs of vertices such that the shortest distances consider only the
vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of an iteration, vertex no. k is added to the set of
intermediate vertices and the set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
/* A utility function to print solution */
void printSolution(int dist[][V])
{
printf ("The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
186
Chapter 16. DP-16 | Floyd Warshall Algorithm
}
printf("\n");
}
}
// driver program to test above function
int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
// Print the solution
floydWarshall(graph);
return 0;
}
Java
187
Chapter 16. DP-16 | Floyd Warshall Algorithm
188
Chapter 16. DP-16 | Floyd Warshall Algorithm
}
System.out.println();
}
}
// Driver program to test above function
public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
AllPairShortestPath a = new AllPairShortestPath();
// Print the solution
a.floydWarshall(graph);
}
}
// Contributed by Aakash Hasija
Python
189
Chapter 16. DP-16 | Floyd Warshall Algorithm
190
Chapter 16. DP-16 | Floyd Warshall Algorithm
C#
191
Chapter 16. DP-16 | Floyd Warshall Algorithm
192
Chapter 16. DP-16 | Floyd Warshall Algorithm
Console.Write("INF ");
} else {
Console.Write(dist[i, j] + " ");
}
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(string[] args)
{
/* Let us create the following
weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int[,] graph = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
AllPairShortestPath a = new AllPairShortestPath();
// Print the solution
a.floydWarshall(graph);
}
}
// This article is contributed by
// Abdul Mateen Mohammed
Output:
Following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
193
Chapter 16. DP-16 | Floyd Warshall Algorithm
#include
Source
https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
194
Chapter 17
DP-17 | Palindrome
Partitioning
This problem is a variation of Matrix Chain Multiplication problem. If the string is palin-
drome, then we simply return 0. Else, like the Matrix Chain Multiplication problem, we try
making cuts at all possible places, recursively calculate the cost for each cut and return the
minimum value.
Let the given string be str and minPalPartion() be the function that returns the fewest cuts
needed for palindrome partitioning. following is the optimal substructure property.
// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.
minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.
195
Chapter 17. DP-17 | Palindrome Partitioning
C/C++
196
Chapter 17. DP-17 | Palindrome Partitioning
Java
197
Chapter 17. DP-17 | Palindrome Partitioning
198
Chapter 17. DP-17 | Palindrome Partitioning
str.charAt(j));
else
P[i][j] = (str.charAt(i) ==
str.charAt(j)) && P[i+1][j-1];
// IF str[i..j] is palindrome, then
// C[i][j] is 0
if (P[i][j] == true)
C[i][j] = 0;
else
{
// Make a cut at every possible
// localtion starting from i to j,
// and get the minimum cost cut.
C[i][j] = Integer.MAX_VALUE;
for (k = i; k <= j - 1; k++)
C[i][j] = Integer.min(C[i][j],
C[i][k] + C[k+1][j] + 1);
}
}
}
// Return the min cut value for complete
// string. i.e., str[0..n-1]
return C[0][n-1];
}
// Driver program to test above function
public static void main(String args[])
{
String str = "ababbbabbababa";
System.out.println("Min cuts needed for "+
"Palindrome Partitioning is "+
minPalPartion(str));
}
}
// This code is contributed by Sumit Ghosh
C#
199
Chapter 17. DP-17 | Palindrome Partitioning
200
Chapter 17. DP-17 | Palindrome Partitioning
Output:
201
Chapter 17. DP-17 | Palindrome Partitioning
C++
202
Chapter 17. DP-17 | Palindrome Partitioning
else
P[i][j] = (str[i] == str[j]) && P[i+1][j-1];
}
}
for (i=0; i<n; i++)
{
if (P[0][i] == true)
C[i] = 0;
else
{
C[i] = INT_MAX;
for(j=0;j<i;j++)
{
if(P[j+1][i] == true && 1+C[j]<C[i])
C[i]=1+C[j];
}
}
}
// Return the min cut value for complete string. i.e., str[0..n-1]
return C[n-1];
}
// Driver program to test above function
int main()
{
char str[] = "ababbbabbababa";
printf("Min cuts needed for Palindrome Partitioning is %d",
minPalPartion(str));
return 0;
}
Java
203
Chapter 17. DP-17 | Palindrome Partitioning
204
Chapter 17. DP-17 | Palindrome Partitioning
C[i] = Integer.MAX_VALUE;
for(j = 0; j < i; j++)
{
if(P[j+1][i] == true && 1 +
C[j] < C[i])
C[i] = 1 + C[j];
}
}
}
// Return the min cut value for complete
// string. i.e., str[0..n-1]
return C[n-1];
}
// Driver program to test above function
public static void main(String args[])
{
String str = "ababbbabbababa";
System.out.println("Min cuts needed for "+
"Palindrome Partitioning"+
" is "+ minPalPartion(str));
}
}
// This code is contributed by Sumit Ghosh
C#
205
Chapter 17. DP-17 | Palindrome Partitioning
206
Chapter 17. DP-17 | Palindrome Partitioning
}
}
// Return the min cut value for complete
// string. i.e., str[0..n-1]
return C[n-1];
}
// Driver program
public static void Main()
{
String str = "ababbbabbababa";
Console.Write("Min cuts needed for "+
"Palindrome Partitioning"+
" is "+ minPalPartion(str));
}
}
// This code is contributed by Sam007
Output:
Source
https://www.geeksforgeeks.org/palindrome-partitioning-dp-17/
207
Chapter 18
arr[] = {1, 5, 3}
Output: false
The array cannot be partitioned into equal sum sets.
208
Chapter 18. DP-18 | Partition problem
C/C++
209
Chapter 18. DP-18 | Partition problem
if (sum%2 != 0)
return false;
// Find if there is subset with sum equal to
// half of total sum
return isSubsetSum (arr, n, sum/2);
}
// Driver program to test above function
int main()
{
int arr[] = {3, 1, 5, 9, 12};
int n = sizeof(arr)/sizeof(arr[0]);
if (findPartiion(arr, n) == true)
printf("Can be divided into two subsets "
"of equal sum");
else
printf("Can not be divided into two subsets"
" of equal sum");
return 0;
}
Java
210
Chapter 18. DP-18 | Partition problem
Python3
211
Chapter 18. DP-18 | Partition problem
C#
212
Chapter 18. DP-18 | Partition problem
class GFG
{
// A utility function that returns true if there is a
// subset of arr[] with sun equal to given sum
static bool isSubsetSum (int []arr, int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
// If last element is greater than sum, then ignore it
if (arr[n-1] > sum)
return isSubsetSum (arr, n-1, sum);
/* else, check if sum can be obtained by any of
the following
(a) including the last element
(b) excluding the last element
*/
return isSubsetSum (arr, n-1, sum) ||
isSubsetSum (arr, n-1, sum-arr[n-1]);
}
// Returns true if arr[] can be partitioned in two
// subsets of equal sum, otherwise false
static bool findPartition (int []arr, int n)
{
// Calculate sum of the elements in array
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// If sum is odd, there cannot be two subsets
// with equal sum
if (sum%2 != 0)
return false;
// Find if there is subset with sum equal to half
// of total sum
return isSubsetSum (arr, n, sum/2);
}
// Driver function
public static void Main ()
{
213
Chapter 18. DP-18 | Partition problem
int []arr = {3, 1, 5, 9, 12};
int n = arr.Length;
if (findPartition(arr, n) == true)
Console.Write("Can be divided into two "+
"subsets of equal sum");
else
Console.Write("Can not be divided into " +
"two subsets of equal sum");
}
}
// This code is contributed by Sam007
Output:
Time Complexity: O(2^n) In worst case, this solution tries two possibilities (whether to
include or exclude) for every element.
Dynamic Programming Solution
The problem can be solved using dynamic programming when the sum of the elements is
not too big. We can create a 2D array part[][] of size (sum/2)*(n+1). And we can construct
the solution in bottom up manner such that every filled entry has following property
C/C++
214
Chapter 18. DP-18 | Partition problem
if (sum%2 != 0)
return false;
bool part[sum/2+1][n+1];
// initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true;
// initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false;
// Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
}
/* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */
return part[sum/2][n];
}
// Driver program to test above funtion
int main()
{
int arr[] = {3, 1, 1, 2, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
if (findPartiion(arr, n) == true)
printf("Can be divided into two subsets of equal sum");
else
printf("Can not be divided into two subsets of equal sum");
getchar();
return 0;
}
215
Chapter 18. DP-18 | Partition problem
Java
216
Chapter 18. DP-18 | Partition problem
printf("\n");
} */
return part[sum/2][n];
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {3, 1, 1, 2, 2,1};
int n = arr.length;
if (findPartition(arr, n) == true)
System.out.println("Can be divided into two "
"subsets of equal sum");
else
System.out.println("Can not be divided into"
" two subsets of equal sum");
}
}
/* This code is contributed by Devesh Agrawal */
C#
217
Chapter 18. DP-18 | Partition problem
218
Chapter 18. DP-18 | Partition problem
}
}
// This code is contributed by Sam007.
Output:
Source
https://www.geeksforgeeks.org/partition-problem-dp-18/
219
Chapter 19
The extra spaces includes spaces put at the end of every line except the last one.
The problem is to minimize the following total cost.
Cost of a line = (Number of extra spaces in the line)^3
Total Cost = Sum of costs for all lines
The total extra spaces in line 1, line 2 and line 3 are 0, 2 and 3 respectively.
So optimal value of total cost is 0 + 2*2 + 3*3 = 13
Please note that the total cost function is not sum of extra spaces, but sum of cubes (or
square is also used) of extra spaces. The idea behind this cost function is to balance the
spaces among lines. For example, consider the following two arrangement of same set of
words:
220
Chapter 19. DP-19 | Word Wrap Problem
1) There are 3 lines. One line has 3 extra spaces and all other lines have 0 extra spaces.
Total extra spaces = 3 + 0 + 0 = 3. Total cost = 3*3*3 + 0*0*0 + 0*0*0 = 27.
2) There are 3 lines. Each of the 3 lines has one extra space. Total extra spaces = 1 + 1 +
1 = 3. Total cost = 1*1*1 + 1*1*1 + 1*1*1 = 3.
Total extra spaces are 3 in both scenarios, but second arrangement should be preferred
because extra spaces are balanced in all three lines. The cost function with cubic sum
serves the purpose because the value of total cost in second scenario is less.
Method 1 (Greedy Solution)
The greedy solution is to place as many words as possible in the first line. Then do the
same thing for the second line and so on until all words are placed. This solution gives
optimal solution for many cases, but doesn’t give optimal solution in all cases. For example,
consider the following string “aaa bb cc ddddd” and line width as 6. Greedy method will
produce following output.
aaa bb
cc
ddddd
Extra spaces in the above 3 lines are 0, 4 and 1 respectively. So total cost is 0 + 64 + 1 =
65.
But the above solution is not the best solution. Following arrangement has more balanced
spaces. Therefore less value of total cost function.
aaa
bb cc
ddddd
Extra spaces in the above 3 lines are 3, 1 and 1 respectively. So total cost is 27 + 1 + 1 =
29.
Despite being sub-optimal in some cases, the greedy approach is used by many word pro-
cessors like MS Word and OpenOffice.org Writer.
Method 2 (Dynamic Programming)
The following Dynamic approach strictly follows the algorithm given in solution of Cormen
book. First we compute costs of all possible lines in a 2D table lc[][]. The value lc[i][j]
indicates the cost to put words from i to j in a single line where i and j are indexes of words
in the input sequences. If a sequence of words from i to j cannot fit in a single line, then
lc[i][j] is considered infinite (to avoid it from being a part of the solution). Once we have
the lc[][] table constructed, we can calculate total cost using following recursive formula. In
the following formula, C[j] is the optimized total cost for arranging words from 1 to j.
221
Chapter 19. DP-19 | Word Wrap Problem
The above recursion has overlapping subproblem property. For example, the solution of
subproblem c(2) is used by c(3), C(4) and so on. So Dynamic Programming is used to store
the results of subproblems. The array c[] can be computed from left to right, since each
value depends only on earlier values.
To print the output, we keep track of what words go on what lines, we can keep a parallel
p array that points to where each c value came from. The last line starts at word p[n] and
goes through word n. The previous line starts at word p[p[n]] and goes through word p[n?]
– 1, etc. The function printSolution() uses p[] to print the solution.
In the below program, input is an array l[] that represents lengths of words in a sequence.
The value l[i] indicates length of the ith word (i starts from 1) in theinput sequence.
C/C++
222
Chapter 19. DP-19 | Word Wrap Problem
223
Chapter 19. DP-19 | Word Wrap Problem
printSolution(p, n);
}
int printSolution (int p[], int n)
{
int k;
if (p[n] == 1)
k = 1;
else
k = printSolution (p, p[n]-1) + 1;
printf ("Line number %d: From word no. %d to %d \n", k, p[n], n);
return k;
}
// Driver program to test above functions
int main()
{
int l[] = {3, 2, 2, 5};
int n = sizeof(l)/sizeof(l[0]);
int M = 6;
solveWordWrap (l, n, M);
return 0;
}
Java
224
Chapter 19. DP-19 | Word Wrap Problem
// l[] and M is line width (maximum no. of characters that can fit in a line)
void solveWordWrap (int l[], int n, int M)
{
// For simplicity, 1 extra space is used in all below arrays
// extras[i][j] will have number of extra spaces if words from i
// to j are put in a single line
int extras[][] = new int[n+1][n+1];
// lc[i][j] will have cost of a line which has words from
// i to j
int lc[][]= new int[n+1][n+1];
// c[i] will have total cost of optimal arrangement of words
// from 1 to i
int c[] = new int[n+1];
// p[] is used to print the solution.
int p[] =new int[n+1];
// calculate extra spaces in a single line. The value extra[i][j]
// indicates extra spaces if words from word number i to j are
// placed in a single line
for (int i = 1; i <= n; i++)
{
extras[i][i] = M - l[i-1];
for (int j = i+1; j <= n; j++)
extras[i][j] = extras[i][j-1] - l[j-1] - 1;
}
// Calculate line cost corresponding to the above calculated extra
// spaces. The value lc[i][j] indicates cost of putting words from
// word number i to j in a single line
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
if (extras[i][j] < 0)
lc[i][j] = MAX;
else if (j == n && extras[i][j] >= 0)
lc[i][j] = 0;
else
lc[i][j] = extras[i][j]*extras[i][j];
}
}
// Calculate minimum cost and find minimum cost arrangement.
// The value c[j] indicates optimized cost to arrange words
225
Chapter 19. DP-19 | Word Wrap Problem
C#
226
Chapter 19. DP-19 | Word Wrap Problem
227
Chapter 19. DP-19 | Word Wrap Problem
- l[j-1] - 1;
}
// Calculate line cost corresponding to
// the above calculated extra spaces. The
// value lc[i][j] indicates cost of
// putting words from word number i to
// j in a single line
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
if (extras[i,j] < 0)
lc[i,j] = MAX;
else if (j == n &&
extras[i,j] >= 0)
lc[i,j] = 0;
else
lc[i,j] = extras[i,j]
* extras[i,j];
}
}
// Calculate minimum cost and find
// minimum cost arrangement. The value
// c[j] indicates optimized cost to
// arrange words from word number
// 1 to j.
c[0] = 0;
for (int j = 1; j <= n; j++)
{
c[j] = MAX;
for (int i = 1; i <= j; i++)
{
if (c[i-1] != MAX && lc[i,j]
!= MAX && (c[i-1] + lc[i,j]
< c[j]))
{
c[j] = c[i-1] + lc[i,j];
p[j] = i;
}
}
}
printSolution(p, n);
}
// Driver code
228
Chapter 19. DP-19 | Word Wrap Problem
Output:
Source
https://www.geeksforgeeks.org/word-wrap-problem-dp-19/
229
Chapter 20
#include<stdio.h>
#include<stdlib.h>
// Structure for a pair
struct pair
{
int a;
int b;
};
230
Chapter 20. DP-20 | Maximum Length Chain of Pairs
// This function assumes that arr[] is sorted in increasing order
// according the first (or smaller) values in pairs.
int maxChainLength( struct pair arr[], int n)
{
int i, j, max = 0;
int *mcl = (int*) malloc ( sizeof( int ) * n );
/* Initialize MCL (max chain length) values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain length values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b && mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum chain length ending with pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
/* Free memory to avoid memory leak */
free( mcl );
return max;
}
/* Driver program to test above function */
int main()
{
struct pair arr[] = { {5, 24}, {15, 25},
{27, 40}, {50, 60} };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of maximum size chain is %d\n",
maxChainLength( arr, n ));
return 0;
}
Java
class Pair{
int a;
int b;
231
Chapter 20. DP-20 | Maximum Length Chain of Pairs
public Pair(int a, int b) {
this.a = a;
this.b = b;
}
// This function assumes that arr[] is sorted in increasing order
// according the first (or smaller) values in pairs.
static int maxChainLength(Pair arr[], int n)
{
int i, j, max = 0;
int mcl[] = new int[n];
/* Initialize MCL (max chain length) values for all indexes */
for ( i = 0; i < n; i++ )
mcl[i] = 1;
/* Compute optimized chain length values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i].a > arr[j].b && mcl[i] < mcl[j] + 1)
mcl[i] = mcl[j] + 1;
// mcl[i] now stores the maximum chain length ending with pair i
/* Pick maximum of all MCL values */
for ( i = 0; i < n; i++ )
if ( max < mcl[i] )
max = mcl[i];
return max;
}
/* Driver program to test above function */
public static void main(String[] args)
{
Pair arr[] = new Pair[] {new Pair(5,24), new Pair(15, 25),
new Pair (27, 40), new Pair(50, 60)};
System.out.println("Length of maximum size chain is " +
maxChainLength(arr, arr.length));
}
}
Python3
class Pair(object):
def __init__(self, a, b):
self.a = a
232
Chapter 20. DP-20 | Maximum Length Chain of Pairs
self.b = b
# This function assumes that arr[] is sorted in increasing
# order according the first (or smaller) values in pairs.
def maxChainLength(arr, n):
max = 0
# Initialize MCL(max chain length) values for all indices
mcl = [1 for i in range(n)]
# Compute optimized chain length values in bottom up manner
for i in range(1, n):
for j in range(0, i):
if (arr[i].a > arr[j].b and mcl[i] < mcl[j] + 1):
mcl[i] = mcl[j] + 1
# mcl[i] now stores the maximum
# chain length ending with pair i
# Pick maximum of all MCL values
for i in range(n):
if (max < mcl[i]):
max = mcl[i]
return max
# Driver program to test above function
arr = [Pair(5, 24), Pair(15, 25), Pair(27, 40), Pair(50, 60)]
print('Length of maximum size chain is',
maxChainLength(arr, len(arr)))
# This code is contributed by Soumen Ghosh
C#
233
Chapter 20. DP-20 | Maximum Length Chain of Pairs
this.b = b;
}
// This function assumes that arr[]
// is sorted in increasing order
// according the first (or smaller)
// values in pairs.
static int maxChainLength(Pair []arr, int n)
{
int i, j, max = 0;
int []mcl = new int[n];
// Initialize MCL (max chain length)
// values for all indexes
for(i = 0; i < n; i++ )
mcl[i] = 1;
// Compute optimized chain length
// values in bottom up manner
for(i = 1; i < n; i++)
for (j = 0; j < i; j++)
if(arr[i].a > arr[j].b &&
mcl[i] < mcl[j] + 1)
// mcl[i] now stores the maximum
// chain length ending with pair i
mcl[i] = mcl[j] + 1;
// Pick maximum of all MCL values
for ( i = 0; i < n; i++ )
if (max < mcl[i] )
max = mcl[i];
return max;
}
// Driver Code
public static void Main()
{
Pair []arr = new Pair[] {new Pair(5,24), new Pair(15, 25),
new Pair (27, 40), new Pair(50, 60)};
Console.Write("Length of maximum size chain is " +
maxChainLength(arr, arr.Length));
}
}
// This code is contributed by nitin mittal.
234
Chapter 20. DP-20 | Maximum Length Chain of Pairs
Output:
Source
https://www.geeksforgeeks.org/maximum-length-chain-of-pairs-dp-20/
235
Chapter 21
8 1 4 3 5 2 6 7
--------------------------------------------
--------------------------------------------
1 2 3 4 5 6 7 8
Source:Dynamic Programming Practice Problems. The link also has well explained solution
for the problem.
2. Maximum Sum Increasing Subsequence: Given an array of n positive integers.
Write a program to find the maximum sum subsequence of the given array such that the
intgers in the subsequence are sorted in increasing order. For example, if input is {1, 101, 2,
3, 100, 4, 5}, then output should be {1, 2, 3, 100}. The solution to this problem has been
published here.
3. The Longest Chain You are given pairs of numbers. In a pair, the first number is
smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d),
236
Chapter 21. DP-21 | Variations of LIS
the second set can follow the first set if b < c. So you can form a long chain in the similar
fashion. Find the longest chain which can be formed. The solution to this problem has been
published here.
4. Box Stacking You are given a set of n types of rectangular 3-D boxes, where the i^th
box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a
stack of boxes which is as tall as possible, but you can only stack a box on top of another
box if the dimensions of the 2-D base of the lower box are each strictly larger than those of
the 2-D base of the higher box. Of course, you can rotate a box so that any side functions
as its base. It is also allowable to use multiple instances of the same type of box.
Source:Dynamic Programming Practice Problems. The link also has well explained solution
for the problem.
Please write comments if you find anything incorrect, or you want to share more information
about the topic discussed above.
Source
https://www.geeksforgeeks.org/variations-of-lis-dp-21/
237
Chapter 22
238
Chapter 22. DP-22 | Box Stacking Problem
The Box Stacking problem is a variation of LIS problem. We need to build a maximum
height stack.
Following are the key points to note in the problem statement:
1) A box can be placed on top of another box only if both width and depth of the upper
placed box are smaller than width and depth of the lower box respectively.
2) We can rotate boxes such that width is smaller than depth. For example, if there is a box
with dimensions {1x2x3} where 1 is height, 2×3 is base, then there can be three possibilities,
{1x2x3}, {2x1x3} and {3x1x2}
3) We can use multiple instances of boxes. What it means is, we can have two different
rotations of a box as part of our maximum height stack.
239
Chapter 22. DP-22 | Box Stacking Problem
C++
240
Chapter 22. DP-22 | Box Stacking Problem
241
Chapter 22. DP-22 | Box Stacking Problem
Java
242
Chapter 22. DP-22 | Box Stacking Problem
/*Constructor to initialise object*/
public Box(int h, int w, int d) {
this.h = h;
this.w = w;
this.d = d;
}
/*To sort the box array on the basis
of area in decreasing order of area */
@Override
public int compareTo(Box o) {
return o.area-this.area;
}
}
/* Returns the height of the tallest
stack that can be formed with give
type of boxes */
static int maxStackHeight( Box arr[], int n){
Box[] rot = new Box[n*3];
/* New Array of boxes is created -
considering all 3 possible rotations,
with width always greater than equal
to width */
for(int i = 0;i < n;i++){
Box box = arr[i];
/* Orignal Box*/
rot[3*i] = new Box(box.h, Math.max(box.w,box.d),
Math.min(box.w,box.d));
/* First rotation of box*/
rot[3*i + 1] = new Box(box.w, Math.max(box.h,box.d),
Math.min(box.h,box.d));
/* Second rotation of box*/
rot[3*i + 2] = new Box(box.d, Math.max(box.w,box.h),
Math.min(box.w,box.h));
}
/* Calculating base area of
each of the boxes.*/
for(int i = 0; i < rot.length; i++)
rot[i].area = rot[i].w * rot[i].d;
243
Chapter 22. DP-22 | Box Stacking Problem
244
Chapter 22. DP-22 | Box Stacking Problem
System.out.println("The maximum possible "+
"height of stack is " +
maxStackHeight(arr,4));
}
}
// This code is contributed by Divyam
Output:
In the above program, given input boxes are {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}.
Following are all rotations of the boxes in decreasing order of base area.
10 x 12 x 32
12 x 10 x 32
32 x 10 x 12
4 x 6 x 7
4 x 5 x 6
6 x 4 x 7
5 x 4 x 6
7 x 4 x 6
6 x 4 x 5
1 x 2 x 3
2 x 1 x 3
3 x 1 x 2
The height 60 is obtained by boxes { {3, 1, 2}, {1, 2, 3}, {6, 4, 5}, {4, 5, 6}, {4, 6, 7}, {32,
10, 12}, {10, 12, 32}}
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Source
https://www.geeksforgeeks.org/box-stacking-problem-dp-22/
245
Chapter 23
DP-23 | Bellman–Ford
Algorithm
246
Chapter 23. DP-23 | Bellman–Ford Algorithm
How does this work? Like other Dynamic Programming Problems, the algorithm calcu-
late shortest paths in bottom-up manner. It first calculates the shortest distances which
have at-most one edge in the path. Then, it calculates shortest paths with at-most 2 edges,
and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges
are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the
outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle,
if we have calculated shortest paths with at most i edges, then an iteration over all edges
guarantees to give shortest path with at-most (i+1) edges (Proof is simple, you can refer
this or MIT Video Lecture)
Example
Let us understand the algorithm with following example graph. The images are taken from
thissource.
Let the given source vertex be 0. Initialize all distances as infinite, except the distance to
source itself. Total number of vertices in the graph is 5, so all edges must be processed 4
times.
Let all edges are processed in following order: (B,E), (D,B), (B,D), (A,B), (A,C), (D,C),
(B,C), (E,D). We get following distances when all edges are processed first time. The first
row in shows initial distances. The second row shows distances when edges (B,E), (D,B),
(B,D) and (A,B) are processed. The third row shows distances when (A,C) is processed.
The fourth row shows when (D,C), (B,C) and (E,D) are processed.
247
Chapter 23. DP-23 | Bellman–Ford Algorithm
The first iteration guarantees to give all shortest paths which are at most 1 edge long. We
get following distances when all edges are processed second time (The last row shows final
values).
The second iteration guarantees to give all shortest paths which are at most 2 edges long.
The algorithm processes all edges 2 more times. The distances are minimized after the
second iteration, so third and fourth iterations don’t update the distances.
Implementation:
C++
248
Chapter 23. DP-23 | Bellman–Ford Algorithm
249
Chapter 23. DP-23 | Bellman–Ford Algorithm
250
Chapter 23. DP-23 | Bellman–Ford Algorithm
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}
Java
251
Chapter 23. DP-23 | Bellman–Ford Algorithm
import java.util.*;
import java.lang.*;
import java.io.*;
// A class to represent a connected, directed and weighted graph
class Graph
{
// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Graph graph,int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i=0; i<V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can
// have at-most |V| - 1 edges
for (int i=1; i<V; ++i)
{
for (int j=0; j<E; ++j)
252
Chapter 23. DP-23 | Bellman–Ford Algorithm
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u]!=Integer.MAX_VALUE &&
dist[u]+weight<dist[v])
dist[v]=dist[u]+weight;
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE &&
dist[u]+weight < dist[v])
System.out.println("Graph contains negative weight cycle");
}
printArr(dist, V);
}
// A utility function used to print the solution
void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i=0; i<V; ++i)
System.out.println(i+"\t\t"+dist[i]);
}
// Driver method to test above function
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
253
Chapter 23. DP-23 | Bellman–Ford Algorithm
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
}
// Contributed by Aakash Hasija
Python
254
Chapter 23. DP-23 | Bellman–Ford Algorithm
def __init__(self,vertices):
self.V= vertices #No. of vertices
self.graph = [] # default dictionary to store graph
# function to add an edge to graph
def addEdge(self,u,v,w):
self.graph.append([u, v, w])
# utility function used to print the solution
def printArr(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("%d \t\t %d" % (i, dist[i]))
# The main function that finds shortest distances from src to
# all other vertices using Bellman-Ford algorithm. The function
# also detects negative weight cycle
def BellmanFord(self, src):
# Step 1: Initialize distances from src to all other vertices
# as INFINITE
dist = [float("Inf")] * self.V
dist[src] = 0
# Step 2: Relax all edges |V| - 1 times. A simple shortest
# path from src to any other vertex can have at-most |V| - 1
# edges
for i in range(self.V - 1):
# Update dist value and parent index of the adjacent vertices of
# the picked vertex. Consider only those vertices which are still in
# queue
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Step 3: check for negative-weight cycles. The above step
# guarantees shortest distances if graph doesn't contain
# negative weight cycle. If we get a shorter path, then there
# is a cycle.
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print "Graph contains negative weight cycle"
return
# print all distance
255
Chapter 23. DP-23 | Bellman–Ford Algorithm
self.printArr(dist)
g = Graph(5)
g.addEdge(0, 1, -1)
g.addEdge(0, 2, 4)
g.addEdge(1, 2, 3)
g.addEdge(1, 3, 2)
g.addEdge(1, 4, 2)
g.addEdge(3, 2, 5)
g.addEdge(3, 1, 1)
g.addEdge(4, 3, -3)
#Print the solution
g.BellmanFord(0)
#This code is contributed by Neelam Yadav
Output:
Notes
1) Negative weights are found in various applications of graphs. For example, instead of
paying cost for a path, we may get some advantage if we follow the path.
2) Bellman-Ford works better (better than Dijksra’s) for distributed systems. Unlike Di-
jksra’s where we need to find minimum value of all vertices, in Bellman-Ford, edges are
considered one by one.
Exercise
1) The standard Bellman-Ford algorithm reports shortest path only if there is no negative
weight cycles. Modify it so that it reports minimum distances even if there is a negative
weight cycle.
2) Can we use Dijksra’s algorithm for shortest paths for graphs with negative weights – one
idea can be, calculate the minimum weight value, add a positive value (equal to absolute
value of minimum weight value) to all weights and run the Dijksra’s algorithm for the
modified graph. Will this algorithm work?
References:
http://www.youtube.com/watch?v=Ttezuzs39nk
http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
http://www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf
256
Chapter 23. DP-23 | Bellman–Ford Algorithm
Source
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
257
Chapter 24
Example 1
Input: keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs
10 12
\ /
12 10
I II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118
Example 2
Input: keys[] = {10, 12, 20}, freq[] = {34, 8, 50}
There can be following possible BSTs
10 12 20 10 20
\ / \ / \ /
12 10 20 12 20 10
\ / / \
20 10 12 12
I II III IV V
258
Chapter 24. DP-24 | Optimal Binary Search Tree
1) Optimal Substructure:
The optimal cost for freq[i..j] can be recursively calculated using following formula.
C/C++
259
Chapter 24. DP-24 | Optimal Binary Search Tree
Java
260
Chapter 24. DP-24 | Optimal Binary Search Tree
261
Chapter 24. DP-24 | Optimal Binary Search Tree
C#
262
Chapter 24. DP-24 | Optimal Binary Search Tree
263
Chapter 24. DP-24 | Optimal Binary Search Tree
Output:
Time complexity of the above naive recursive approach is exponential. It should be noted
that the above function computes the same subproblems again and again. We can see many
subproblems being repeated in the following recursion tree for freq[1..4].
Since same suproblems are called again, this problem has Overlapping Subprolems property.
So optimal BST problem has both properties (see thisand this) of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, recomputations of same
subproblems can be avoided by constructing a temporary array cost[][] in bottom up manner.
Dynamic Programming Solution
Following is C/C++ implementation for optimal BST problem using Dynamic Programming.
We use an auxiliary array cost[n][n] to store the solutions of subproblems. cost[0][n-1] will
hold the final result. The challenge in implementation is, all diagonal values must be filled
first, then the values which lie on the line just above the diagonal. In other words, we must
first fill all cost[i][i] values, then all cost[i][i+1] values, then all cost[i][i+2] values. So how to
fill the 2D array in such manner> The idea used in the implementation is same as Matrix
Chain Multiplication problem, we use a variable ‘L’ for chain length and increment ‘L’, one
by one. We calculate column number ‘j’ using the values of ‘i’ and ‘L’.
C/C++
264
Chapter 24. DP-24 | Optimal Binary Search Tree
#include <limits.h>
// A utility function to get sum of array elements
// freq[i] to freq[j]
int sum(int freq[], int i, int j);
/* A Dynamic Programming based function that calculates
minimum cost of a Binary Search Tree. */
int optimalSearchTree(int keys[], int freq[], int n)
{
/* Create an auxiliary 2D matrix to store results
of subproblems */
int cost[n][n];
/* cost[i][j] = Optimal cost of binary search tree
that can be formed from keys[i] to keys[j].
cost[0][n-1] will store the resultant cost */
// For a single key, cost is equal to frequency of the key
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
// Now we need to consider chains of length 2, 3, ... .
// L is chain length.
for (int L=2; L<=n; L++)
{
// i is row number in cost[][]
for (int i=0; i<=n-L+1; i++)
{
// Get column number j from row number i and
// chain length L
int j = i+L-1;
cost[i][j] = INT_MAX;
// Try making all keys in interval keys[i..j] as root
for (int r=i; r<=j; r++)
{
// c = cost when keys[r] becomes root of this subtree
int c = ((r > i)? cost[i][r-1]:0) +
((r < j)? cost[r+1][j]:0) +
sum(freq, i, j);
if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[0][n-1];
}
265
Chapter 24. DP-24 | Optimal Binary Search Tree
// A utility function to get sum of array elements
// freq[i] to freq[j]
int sum(int freq[], int i, int j)
{
int s = 0;
for (int k = i; k <=j; k++)
s += freq[k];
return s;
}
// Driver program to test above functions
int main()
{
int keys[] = {10, 12, 20};
int freq[] = {34, 8, 50};
int n = sizeof(keys)/sizeof(keys[0]);
printf("Cost of Optimal BST is %d ",
optimalSearchTree(keys, freq, n));
return 0;
}
Java
266
Chapter 24. DP-24 | Optimal Binary Search Tree
C#
267
Chapter 24. DP-24 | Optimal Binary Search Tree
268
Chapter 24. DP-24 | Optimal Binary Search Tree
Output:
Notes
1) The time complexity of the above solution is O(n^4). The time complexity can be easily
reduced to O(n^3) by pre-calculating sum of frequencies instead of calling sum() again and
again.
2) In the above solutions, we have computed optimal cost only. The solutions can be easily
modified to store the structure of BSTs also. We can create another auxiliary array of size
n to store the structure of tree. All we need to do is, store the chosen ‘r’ in the innermost
loop.
Please write comments if you find anything incorrect, or you want to share more information
about the topic discussed above.
Improved By : aradhya95
Source
https://www.geeksforgeeks.org/optimal-binary-search-tree-dp-24/
269
Chapter 25
Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset
of set[] with sum equal to sum. n is the number of elements in set[].
The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.
Following is the recursive formula for isSubsetSum() problem.
270
Chapter 25. DP-25 | Subset Sum Problem
Following is naive recursive implementation that simply follows the recursive structure
mentioned above.
271
Chapter 25. DP-25 | Subset Sum Problem
Java
272
Chapter 25. DP-25 | Subset Sum Problem
Python3
C#
273
Chapter 25. DP-25 | Subset Sum Problem
using System;
class GFG
{
// Returns true if there is a subset of set[] with sum
// equal to given sum
static bool isSubsetSum(int []set, int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n-1] > sum)
return isSubsetSum(set, n-1, sum);
/* else, check if sum can be obtained
by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1]);
}
// Driver program
public static void Main ()
{
int []set = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.Length;
if (isSubsetSum(set, n, sum) == true)
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}
// This code is contributed by Sam007
PHP
<?php
// A recursive solution for subset sum problem
// Returns true if there is a subset of set
274
Chapter 25. DP-25 | Subset Sum Problem
Output:
The above solution may try all subsets of given set in worst case. Therefore time complexity
of the above solution is exponential. The problem is in-fact NP-Complete (There is no
known polynomial time solution for this problem).
We can solve the problem in Pseudo-polynomial time using Dynamic program-
ming. We create a boolean 2D table subset[][] and fill it in bottom up manner. The value
of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise
275
Chapter 25. DP-25 | Subset Sum Problem
276
Chapter 25. DP-25 | Subset Sum Problem
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}
// This code is contributed by Arjun Tyagi.
Java
277
Chapter 25. DP-25 | Subset Sum Problem
}
}
/* // uncomment this code to print table
for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
System.out.println (subset[i][j]);
} */
return subset[sum][n];
}
/* Driver program to test above function */
public static void main (String args[])
{
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
}
}
/* This code is contributed by Rajat Mishra */
C#
278
Chapter 25. DP-25 | Subset Sum Problem
// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[i, 0] = false;
// Fill the subset table in botton up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i, j] = subset[i, j - 1];
if (i >= set[j - 1])
subset[i, j] = subset[i, j] ||
subset[i - set[j - 1], j - 1];
}
}
return subset[sum,n];
}
// Driver program
public static void Main ()
{
int []set = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.Length;
if (isSubsetSum(set, n, sum) == true)
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}
// This code is contributed by Sam007
PHP
<?php
// A Dynamic Programming solution for
// subset sum problem
// Returns true if there is a subset of
// set[] with sun equal to given sum
function isSubsetSum( $set, $n, $sum)
{
// The value of subset[i][j] will
// be true if there is a subset of
// set[0..j-1] with sum equal to i
279
Chapter 25. DP-25 | Subset Sum Problem
$subset = array(array());
// If sum is 0, then answer is true
for ( $i = 0; $i <= $n; $i++)
$subset[$i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for ( $i = 1; $i <= $sum; $i++)
$subset[0][$i] = false;
// Fill the subset table in botton
// up manner
for ($i = 1; $i <= $n; $i++)
{
for ($j = 1; $j <= $sum; $j++)
{
if($j < $set[$i-1])
$subset[$i][$j] =
$subset[$i-1][$j];
if ($j >= $set[$i-1])
$subset[$i][$j] =
$subset[$i-1][$j] ||
$subset[$i - 1][$j -
$set[$i-1]];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
printf("n");
}*/
return $subset[$n][$sum];
}
// Driver program to test above function
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
echo "Found a subset with given sum";
else
echo "No subset with given sum";
280
Chapter 25. DP-25 | Subset Sum Problem
// This code is contributed by anuj_67.
?>
Output:
Time complexity of the above solution is O(sum*n).Subset Sum Problem in O(sum) space
Perfect Sum Problem (Print all subsets with given sum)
Improved By : vt_m
Source
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
281
Chapter 26
282
Chapter 26. DP-26 | Largest Independent Set Problem
The idea is simple, there are two possibilities for every node X, either X is a member of
the set or not a member. If X is a member, then the value of LISS(X) is 1 plus LISS of all
grandchildren. If X is not a member, then the value is sum of LISS of all children.
2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned
above.
283
Chapter 26. DP-26 | Largest Independent Set Problem
// A utility function to create a node
struct node* newNode( int data )
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
struct node *root = newNode(20);
root->left = newNode(8);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
root->right = newNode(22);
root->right->right = newNode(25);
printf ("Size of the Largest Independent Set is %d ", LISS(root));
return 0;
}
Output:
Time complexity of the above naive recursive approach is exponential. It should be noted
that the above function computes the same subproblems again and again. For example,
LISS of node with value 50 is evaluated for node with values 10 and 20 as 50 is grandchild
of 10 and child of 20.
Since same suproblems are called again, this problem has Overlapping Subprolems prop-
erty. So LISS problem has both properties (see thisand this) of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, recomputations of same
subproblems can be avoided by storing the solutions to subproblems and solving problems
in bottom up manner.
Following is C implementation of Dynamic Programming based solution. In the following
solution, an additional field ‘liss’ is added to tree nodes. The initial value of ‘liss’ is set as
0 for all nodes. The recursive function LISS() calculates ‘liss’ for a node only if it is not
already set.
C
284
Chapter 26. DP-26 | Largest Independent Set Problem
285
Chapter 26. DP-26 | Largest Independent Set Problem
Java
286
Chapter 26. DP-26 | Largest Independent Set Problem
287
Chapter 26. DP-26 | Largest Independent Set Problem
// This code is contributed by Rishabh Mahrsee
Output
Time Complexity: O(n) where n is the number of nodes in given Binary tree.
Following extensions to above solution can be tried as an exercise.
1) Extend the above solution for n-ary tree.
2) The above solution modifies the given tree structure by adding an additional field ‘liss’
to tree nodes. Extend the solution so that it doesn’t modify the tree structure.
3) The above solution only returns size of LIS, it doesn’t print elements of LIS. Extend the
solution to print all nodes that are part of LIS.
Source
https://www.geeksforgeeks.org/largest-independent-set-problem-dp-26/
288
Chapter 27
This problem is mainly an extension of Largest Sum Contiguous Subarray for 1D array.
The naive solution for this problem is to check every possible rectangle in given 2D array.
This solution requires 4 nested loops and time complexity of this solution would be O(n^4).
Kadane’s algorithm for 1D array can be used to reduce the time complexity to O(n^3).
The idea is to fix the left and right columns one by one and find the maximum sum
contiguous rows for every left and right column pair. We basically find top and bottom row
numbers (which have maximum sum) for every fixed left and right column pair. To find
the top and bottom row numbers, calculate sun of elements in every row from left to right
and store these sums in an array say temp[]. So temp[i] indicates sum of elements from left
289
Chapter 27. DP-27 | Maximum sum rectangle in a 2D matrix
to right in row i. If we apply Kadane’s 1D algorithm on temp[], and get the maximum sum
subarray of temp, this maximum sum would be the maximum possible sum with left and
right as boundary columns. To get the overall maximum sum, we compare this sum with
the maximum sum so far.
290
Chapter 27. DP-27 | Maximum sum rectangle in a 2D matrix
// Special Case: When all numbers in arr[] are negative
maxSum = arr[0];
*start = *finish = 0;
// Find the maximum element in array
for (i = 1; i < n; i++)
{
if (arr[i] > maxSum)
{
maxSum = arr[i];
*start = *finish = i;
}
}
return maxSum;
}
// The main function that finds maximum sum rectangle in M[][]
void findMaxSum(int M[][COL])
{
// Variables to store the final output
int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
int left, right, i;
int temp[ROW], sum, start, finish;
// Set the left column
for (left = 0; left < COL; ++left)
{
// Initialize all elements of temp as 0
memset(temp, 0, sizeof(temp));
// Set the right column for the left column set by outer loop
for (right = left; right < COL; ++right)
{
// Calculate sum between current left and right for every row 'i'
for (i = 0; i < ROW; ++i)
temp[i] += M[i][right];
// Find the maximum sum subarray in temp[]. The kadane()
// function also sets values of start and finish. So 'sum' is
// sum of rectangle between (start, left) and (finish, right)
// which is the maximum sum with boundary columns strictly as
// left and right.
sum = kadane(temp, &start, &finish, ROW);
// Compare sum with maximum sum so far. If sum is more, then
// update maxSum and other output values
291
Chapter 27. DP-27 | Maximum sum rectangle in a 2D matrix
Java
import java.util.*;
import java.lang.*;
import java.io.*;
/**
* Given a 2D array, find the maximum sum subarray in it
*/
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
findMaxSubMatrix(new int[][] {
{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
292
Chapter 27. DP-27 | Maximum sum rectangle in a 2D matrix
293
Chapter 27. DP-27 | Maximum sum rectangle in a 2D matrix
int[] currentResult;
int maxSum = Integer.MIN_VALUE;
int left = 0;
int top = 0;
int right = 0;
int bottom = 0;
for (int leftCol = 0; leftCol < cols; leftCol++) {
int[] tmp = new int[rows];
for (int rightCol = leftCol; rightCol < cols; rightCol++) {
for (int i = 0; i < rows; i++) {
tmp[i] += a[i][rightCol];
}
currentResult = kadane(tmp);
if (currentResult[0] > maxSum) {
maxSum = currentResult[0];
left = leftCol;
top = currentResult[1];
right = rightCol;
bottom = currentResult[2];
}
}
}
System.out.println("MaxSum: " + maxSum +
", range: [(" + left + ", " + top +
")(" + right + ", " + bottom + ")]");
}
}
// Thanks to Ilia Savin for contributing this code.
Output:
294
Chapter 27. DP-27 | Maximum sum rectangle in a 2D matrix
Source
https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/
295
Chapter 28
Let the input string be str[l……h]. The problem can be broken down into three parts:
1. Find the minimum number of insertions in the substring str[l+1,…….h].
2. Find the minimum number of insertions in the substring str[l…….h-1].
3. Find the minimum number of insertions in the substring str[l+1……h-1].
Recursive Solution
The minimum number of insertions in the string str[l…..h] can be given as:
296
Chapter 28. DP-28 | Minimum insertions to form a palindrome
// palindrome
#include <stdio.h>
#include <limits.h>
#include <string.h>
// A utility function to find minimum of two numbers
int min(int a, int b)
{ return a < b ? a : b; }
// Recursive function to find minimum number of
// insertions
int findMinInsertions(char str[], int l, int h)
{
// Base Cases
if (l > h) return INT_MAX;
if (l == h) return 0;
if (l == h - 1) return (str[l] == str[h])? 0 : 1;
// Check if the first and last characters are
// same. On the basis of the comparison result,
// decide which subrpoblem(s) to call
return (str[l] == str[h])?
findMinInsertions(str, l + 1, h - 1):
(min(findMinInsertions(str, l, h - 1),
findMinInsertions(str, l + 1, h)) + 1);
}
// Driver program to test above functions
int main()
{
char str[] = "geeks";
printf("%d", findMinInsertions(str, 0, strlen(str)-1));
return 0;
}
Java
297
Chapter 28. DP-28 | Minimum insertions to form a palindrome
C#
298
Chapter 28. DP-28 | Minimum insertions to form a palindrome
Output:
abcde
/ | \
/ | \
bcde abcd bcd <- case 3 is discarded as str[l] != str[h]
/ | \ / | \
/ | \ / | \
cde bcd cd bcd abc bc
/ | \ / | \ /|\ / | \
de cd d cd bc c………………….
The substrings in bold show that the recursion to be terminated and the recursion tree cannot
originate from there. Substring in the same color indicates overlapping subproblems.
How to reuse solutions of subproblems?
We can create a table to store results of subproblems so that they can be used directly if
same subproblem is encountered again.
The below table represents the stored values for the string abcde.
299
Chapter 28. DP-28 | Minimum insertions to form a palindrome
a b c d e
----------
0 1 2 3 4
0 0 1 2 3
0 0 0 1 2
0 0 0 0 1
0 0 0 0 0
Gap = 1:
(0, 1) (1, 2) (2, 3) (3, 4)
Gap = 2:
(0, 2) (1, 3) (2, 4)
Gap = 3:
(0, 3) (1, 4)
Gap = 4:
(0, 4)
300
Chapter 28. DP-28 | Minimum insertions to form a palindrome
// Fill the table
for (gap = 1; gap < n; ++gap)
for (l = 0, h = gap; h < n; ++l, ++h)
table[l][h] = (str[l] == str[h])?
table[l+1][h-1] :
(min(table[l][h-1],
table[l+1][h]) + 1);
// Return minimum number of insertions for
// str[0..n-1]
return table[0][n-1];
}
// Driver program to test above function.
int main()
{
char str[] = "geeks";
printf("%d", findMinInsertionsDP(str, strlen(str)));
return 0;
}
Java
301
Chapter 28. DP-28 | Minimum insertions to form a palindrome
table[l+1][h]) + 1);
// Return minimum number of insertions
// for str[0..n-1]
return table[0][n-1];
}
// Driver program to test above function.
public static void main(String args[])
{
String str = "geeks";
System.out.println(
findMinInsertionsDP(str.toCharArray(), str.length()));
}
}
// This code is contributed by Sumit Ghosh
Output:
302
Chapter 28. DP-28 | Minimum insertions to form a palindrome
{
int L[n+1][n+1];
int i, j;
/* Following steps build L[m+1][n+1] in bottom
up fashion. Note that L[i][j] contains length
of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1]
and Y[0..m-1] */
return L[m][n];
}
// LCS based function to find minimum number of
// insertions
int findMinInsertionsLCS(char str[], int n)
{
// Creata another string to store reverse of 'str'
char rev[n+1];
strcpy(rev, str);
strrev(rev);
// The output is length of string minus length of lcs of
// str and it reverse
return (n - lcs(str, rev, n, n));
}
// Driver program to test above functions
int main()
{
char str[] = "geeks";
printf("%d", findMinInsertionsLCS(str, strlen(str)));
return 0;
}
303
Chapter 28. DP-28 | Minimum insertions to form a palindrome
Java
304
Chapter 28. DP-28 | Minimum insertions to form a palindrome
Output:
Time complexity of this method is also O(n^2) and this method also requires O(n^2) extra
space.
Related Article :
Minimum number of Appends needed to make a string palindrome
This article is compiled by Aashish Barnwal. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Improved By : Sam007
Source
https://www.geeksforgeeks.org/minimum-insertions-to-form-a-palindrome-dp-28/
305
Chapter 29
306
Chapter 29. DP-29 | Longest Common Substring
The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m
and 1 <= j <= n
C++
307
Chapter 29. DP-29 | Longest Common Substring
308
Chapter 29. DP-29 | Longest Common Substring
return 0;
}
Java
309
Chapter 29. DP-29 | Longest Common Substring
int m = X.length();
int n = Y.length();
System.out.println("Length of Longest Common Substring is "
+ LCSubStr(X.toCharArray(), Y.toCharArray(), m, n));
}
}
// This code is contributed by Sumit Ghosh
Python3
310
Chapter 29. DP-29 | Longest Common Substring
# Driver Program to test above function
X = 'OldSite:GeeksforGeeks.org'
Y = 'NewSite:GeeksQuiz.com'
m = len(X)
n = len(Y)
print('Length of Longest Common Substring is',
LCSubStr(X, Y, m, n))
# This code is contributed by Soumen Ghosh
C#
311
Chapter 29. DP-29 | Longest Common Substring
LCStuff[i, j] =
LCStuff[i - 1, j - 1] + 1;
result = Math.Max(result,
LCStuff[i, j]);
}
else
LCStuff[i, j] = 0;
}
}
return result;
}
// Driver Program to test above function
public static void Main()
{
String X = "OldSite:GeeksforGeeks.org";
String Y = "NewSite:GeeksQuiz.com";
int m = X.Length;
int n = Y.Length;
Console.Write("Length of Longest Common"
+ " Substring is " + LCSubStr(X, Y, m, n));
}
}
// This code is contributed by Sam007.
Output:
Source
https://www.geeksforgeeks.org/longest-common-substring-dp-29/
312
Chapter 30
Why DP approach?
The above problem exhibits overlapping subproblems. See the below diagram. Also, see
thisrecursive implementation. Let there be 3 dice, each with 6 faces and we need to find the
number of ways to get sum 8:
313
Chapter 30. DP-30 | Dice Throw
Please take a closer look at the above recursion. The sub-problems in RED are solved
first time and sub-problems in BLUE are solved again (exhibit overlapping sub-problems).
Hence, storing the results of the solved sub-problems saves time.
Following is implementation of Dynamic Programming approach.
C++
// C++ program to find number of ways to get sum 'x' with 'n'
// dice where every dice has 'm' faces
#include <iostream>
#include <string.h>
using namespace std;
// The main function that returns number of ways to get sum 'x'
// with 'n' dice and 'm' with m faces.
int findWays(int m, int n, int x)
{
314
Chapter 30. DP-30 | Dice Throw
C#
315
Chapter 30. DP-30 | Dice Throw
class GFG
{
// The main function that returns
// number of ways to get sum 'x'
// with 'n' dice and 'm' with m faces.
static int findWays(int m,
int n, int x)
{
// Create a table to store
// results of subproblems.
// row and column are used
// for simpilicity (Number
// of dice is directly used
// as row index and sum is
// directly used as column
// index). The entries in 0th
// row and 0th column are
// never used.
int[,] table = new int[n + 1,
x + 1];
// Initialize all
// entries as 0
for (int i = 0; i <= n; i++)
for (int j = 0; j <= x; j++)
table[i, j] = 0;
// Table entries for
// only one dice
for (int j = 1;
j <= m && j <= x; j++)
table[1, j] = 1;
// Fill rest of the entries
// in table using recursive
// relation i: number of
// dice, j: sum
for (int i = 2; i <= n; i++)
for (int j = 1; j <= x; j++)
for (int k = 1;
k <= m && k < j; k++)
table[i, j] += table[i - 1,
j - k];
/* Uncomment these lines to
see content of table
for (int i = 0; i <= n; i++)
316
Chapter 30. DP-30 | Dice Throw
{
for (int j = 0; j <= x; j++)
cout << table[i][j] << " ";
cout << endl;
} */
return table[n, x];
}
// Driver Code
public static void Main()
{
Console.WriteLine(findWays(4, 2, 1));
Console.WriteLine(findWays(2, 2, 3));
Console.WriteLine(findWays(6, 3, 8));
Console.WriteLine(findWays(4, 2, 5));
Console.WriteLine(findWays(4, 3, 5));
}
}
// This code is contributed by mits.
PHP
<?php
// PHP program to find number
// of ways to get sum 'x' with
// 'n' dice where every dice
// has 'm' faces
// The main function that returns
// number of ways to get sum 'x'
// with 'n' dice and 'm' with m faces.
function findWays($m, $n, $x)
{
// Create a table to store results
// of subproblems. One extra row
// and column are used for
// simpilicity (Number of dice is
// directly used as row index and
// sum is directly used as column
// index). The entries in 0th row
// and 0th column are never used.
$table;
// Initialize all entries as 0
for ($i = 1; $i < $n + 1; $i++)
for ($j = 1; $j < $x + 1; $j++)
$table[$i][$j] = 0;
317
Chapter 30. DP-30 | Dice Throw
// Table entries for
// only one dice
for ($j = 1; $j <= $m &&
$j <= $x; $j++)
$table[1][$j] = 1;
// Fill rest of the entries
// in table using recursive
// relation i: number of dice,
// j: sum
for ($i = 2; $i <= $n; $i++)
for ($j = 1; $j <= $x; $j++)
for ($k = 1; $k <= $m &&
$k < $j; $k++)
$table[$i][$j] +=
$table[$i - 1][$j - $k];
return $table[$n][$x];
}
// Driver Code
echo findWays(4, 2, 1). "\n";
echo findWays(2, 2, 3). "\n";
echo findWays(6, 3, 8). "\n";
echo findWays(4, 2, 5). "\n";
echo findWays(4, 3, 5). "\n";
// This code is contributed by mits.
?>
Output :
0
2
21
4
6
// When x is so high that sum can not go beyond x even when we
// get maximum value in every dice throw.
318
Chapter 30. DP-30 | Dice Throw
if (m*n <= x)
return (m*n == x);
// When x is too low
if (n >= x)
return (n == x);
With above conditions added, time complexity becomes O(1) when x >= m*n or when x
<= n.
Exercise:
Extend the above algorithm to find the probability to get Sum > X.
This article is compiled by Aashish Barnwal. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Improved By : Mithun Kumar
Source
https://www.geeksforgeeks.org/dice-throw-dp-30/
319
Chapter 31
320
Chapter 31. DP-31 | Optimal Strategy for a Game
So if the user follows the second game state, maximum value can be collected although the
first move is not the best.
There are two choices:
1. The user chooses the ith coin with value Vi: The opponent either chooses (i+1)th coin
or jth coin. The opponent intends to choose the coin which leaves the user with minimum
value.
i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) )
2. The user chooses the jth coin with value Vj: The opponent either chooses ith coin or
(j-1)th coin. The opponent intends to choose the coin which leaves the user with minimum
value.
i.e. The user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) )
Following is recursive solution that is based on above two choices. We take the maximum
of two choices.
F(i, j) represents the maximum value the user can collect from
i'th coin to j'th coin.
321
Chapter 31. DP-31 | Optimal Strategy for a Game
calculated twice.
C++
322
Chapter 31. DP-31 | Optimal Strategy for a Game
Java
323
Chapter 31. DP-31 | Optimal Strategy for a Game
// Driver program
public static void main(String[] args)
{
int arr1[] = { 8, 15, 3, 7 };
int n = arr1.length;
System.out.println("" + optimalStrategyOfGame(arr1, n));
int arr2[] = { 2, 2, 2, 2 };
n = arr2.length;
System.out.println("" + optimalStrategyOfGame(arr2, n));
int arr3[] = { 20, 30, 2, 2, 2, 10 };
n = arr3.length;
System.out.println("" + optimalStrategyOfGame(arr3, n));
}
}
// This code is contributed by vt_m
Output:
22
4
42
Exercise
Your thoughts on the strategy when the user wishes to only win instead of winning with the
maximum value. Like above problem, number of coins is even.
Can Greedy approach work quite well and give an optimal solution? Will your answer
change if number of coins is odd? Please see Coin game of two corners
This article is compiled by Aashish Barnwal. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Source
https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/
324
Chapter 32
Input: ilike
Output: Yes
The string can be segmented as "i like".
Input: ilikesamsung
Output: Yes
The string can be segmented as "i like samsung"
or "i like sam sung".
Recursive implementation:
The idea is simple, we consider each prefix and search it in dictionary. If the prefix is present
in dictionary, we recur for rest of the string (or suffix). If the recursive call for suffix returns
true, we return true, otherwise we try next prefix. If we have tried all prefixes and none of
them resulted in a solution, we return false.
We strongly recommend to see substrfunction which is used extensively in following imple-
mentations.
325
Chapter 32. DP-32 | Word Break Problem
// words in dictionary
#include <iostream>
using namespace std;
/* A utility function to check whether a word is
present in dictionary or not. An array of strings
is used for dictionary. Using array of strings for
dictionary is definitely not a good idea. We have
used for simplicity of the program*/
int dictionaryContains(string word)
{
string dictionary[] = {"mobile","samsung","sam","sung",
"man","mango","icecream","and",
"go","i","like","ice","cream"};
int size = sizeof(dictionary)/sizeof(dictionary[0]);
for (int i = 0; i < size; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}
// returns true if string can be segmented into space
// separated words, otherwise returns false
bool wordBreak(string str)
{
int size = str.size();
// Base case
if (size == 0) return true;
// Try all prefixes of lengths from 1 to size
for (int i=1; i<=size; i++)
{
// The parameter for dictionaryContains is
// str.substr(0, i) which is prefix (of input
// string) of length 'i'. We first check whether
// current prefix is in dictionary. Then we
// recursively check for remaining string
// str.substr(i, size-i) which is suffix of
// length size-i
if (dictionaryContains( str.substr(0, i) ) &&
wordBreak( str.substr(i, size-i) ))
return true;
}
// If we have tried all prefixes and
// none of them worked
return false;
326
Chapter 32. DP-32 | Word Break Problem
}
// Driver program to test above functions
int main()
{
wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";
wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("")? cout <<"Yes\n": cout << "No\n";
wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
return 0;
}
Output:
Yes
Yes
Yes
Yes
Yes
No
Dynamic Programming
Why Dynamic Programming? The above problem exhibits overlapping sub-problems. For
example, see the following partial recursion tree for string “abcde” in worst case.
327
Chapter 32. DP-32 | Word Break Problem
#include <iostream>
#include <string.h>
using namespace std;
/* A utility function to check whether a word is present in dictionary or not.
An array of strings is used for dictionary. Using array of strings for
dictionary is definitely not a good idea. We have used for simplicity of
the program*/
int dictionaryContains(string word)
{
string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
"icecream","and","go","i","like","ice","cream"};
int size = sizeof(dictionary)/sizeof(dictionary[0]);
for (int i = 0; i < size; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}
// Returns true if string can be segmented into space separated
// words, otherwise returns false
bool wordBreak(string str)
{
int size = str.size();
if (size == 0) return true;
// Create the DP table to store results of subroblems. The value wb[i]
// will be true if str[0..i-1] can be segmented into dictionary words,
// otherwise false.
bool wb[size+1];
memset(wb, 0, sizeof(wb)); // Initialize all values as false.
for (int i=1; i<=size; i++)
{
// if wb[i] is false, then check if current prefix can make it true.
// Current prefix is "str.substr(0, i)"
if (wb[i] == false && dictionaryContains( str.substr(0, i) ))
wb[i] = true;
// wb[i] is true, then check for all substrings starting from
// (i+1)th character and store their results.
if (wb[i] == true)
{
// If we reached the last prefix
if (i == size)
return true;
for (int j = i+1; j <= size; j++)
328
Chapter 32. DP-32 | Word Break Problem
{
// Update wb[j] if it is false and can be updated
// Note the parameter passed to dictionaryContains() is
// substring starting from index 'i' and length 'j-i'
if (wb[j] == false && dictionaryContains( str.substr(i, j-i) ))
wb[j] = true;
// If we reached the last character
if (j == size && wb[j] == true)
return true;
}
}
}
/* Uncomment these lines to print DP table "wb[]"
for (int i = 1; i <= size; i++)
cout << " " << wb[i]; */
// If we have tried all prefixes and none of them worked
return false;
}
// Driver program to test above functions
int main()
{
wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";
wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("")? cout <<"Yes\n": cout << "No\n";
wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
return 0;
}
Output:
Yes
Yes
Yes
Yes
Yes
No
329
Chapter 32. DP-32 | Word Break Problem
In this program, we are using some extra space. However, its time complexity is O(n*s)
where s is the length of the largest string in the dictionary and n is the length of the given
string.
330
Chapter 32. DP-32 | Word Break Problem
for (int i = 0; i < n; i++) {
int msize = matched_index.size();
// Flag value which tells that a substring matches
// with given words or not.
int f = 0;
// Check all the substring from the indexes matched
// earlier. If any of that substring matches than
// make flag value = 1;
for (int j = msize - 1; j >= 0; j--) {
// sb is substring starting from matched_index[j]
// + 1 and of length i - matched_index[j]
string sb = s.substr(matched_index[j] + 1, i - matched_index[j]);
if (dictionaryContains(sb)) {
f = 1;
break;
}
}
// If substring matches than do dp[i] = 1 and
// push that index in matched_index array.
if (f == 1) {
dp[i] = 1;
matched_index.push_back(i);
}
}
return dp[n - 1];
}
// Driver code
int main()
{
wordBreak("ilikesamsung") ? cout << "Yes\n" : cout << "No\n";
wordBreak("iiiiiiii") ? cout << "Yes\n" : cout << "No\n";
wordBreak("") ? cout << "Yes\n" : cout << "No\n";
wordBreak("ilikelikeimangoiii") ? cout << "Yes\n" : cout << "No\n";
wordBreak("samsungandmango") ? cout << "Yes\n" : cout << "No\n";
wordBreak("samsungandmangok") ? cout << "Yes\n" : cout << "No\n";
return 0;
}
Output:
331
Chapter 32. DP-32 | Word Break Problem
Yes
Yes
Yes
Yes
Yes
No
Input: ilikeicecreamandmango
Output:
i like ice cream and man go
i like ice cream and mango
i like icecream and man go
i like icecream and mango
Input: ilikesamsungmobile
Output:
i like sam sung mobile
i like samsung mobile
Source
https://www.geeksforgeeks.org/word-break-problem-dp-32/
332
Chapter 33
333
Chapter 33. DP-33 | Find if a string is interleaved of two other strings
Dynamic Programming
The worst case time complexity of recursive solution is O(2n ). The above recursive solution
certainly has many overlapping subproblems. For example, if wee consider A = “XXX”, B
= “XXX” and C = “XXXXXX” and draw recursion tree, there will be many overlapping
subproblems.
Therefore, like other typical Dynamic Programming problems, we can solve it by creating a
table and store results of subproblems in bottom up manner. Thanks to Abhinav Ramana
for suggesting this method and implementation.
334
Chapter 33. DP-33 | Find if a string is interleaved of two other strings
// A is empty
else if (i==0 && B[j-1]==C[j-1])
IL[i][j] = IL[i][j-1];
// B is empty
else if (j==0 && A[i-1]==C[i-1])
IL[i][j] = IL[i-1][j];
// Current character of C matches with current character of A,
// but doesn't match with current character of B
else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1])
IL[i][j] = IL[i-1][j];
// Current character of C matches with current character of B,
// but doesn't match with current character of A
else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1])
IL[i][j] = IL[i][j-1];
// Current character of C matches with that of both A and B
else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])
IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ;
}
}
return IL[M][N];
}
// A function to run test cases
void test(char *A, char *B, char *C)
{
if (isInterleaved(A, B, C))
cout << C <<" is interleaved of " << A <<" and " << B << endl;
else
cout << C <<" is not interleaved of " << A <<" and " << B << endl;
}
// Driver program to test above functions
int main()
{
test("XXY", "XXZ", "XXZXXXY");
test("XY" ,"WZ" ,"WZXY");
test ("XY", "X", "XXY");
test ("YX", "X", "XXY");
test ("XXY", "XXZ", "XXXXZY");
return 0;
}
335
Chapter 33. DP-33 | Find if a string is interleaved of two other strings
Output:
Source
https://www.geeksforgeeks.org/find-if-a-string-is-interleaved-of-two-other-strings-dp-33/
336
Chapter 34
The following information can be extracted from the problem statement to make it simpler:
337
Chapter 34. DP-34 | Assembly Line Scheduling
338
Chapter 34. DP-34 | Assembly Line Scheduling
The total minimum time taken by the car chassis to come out of the factory is given by:
Tmin = min(Time taken to leave station Si,n + Time taken to exit the car factory)
Tmin = min(T1(n) + x1 , T2(n) + x2 )
Why dynamic programming?
The above recursion exhibits overlapping sub-problems. There are two ways to reach station
S1, j :
So, to find the minimum time to leave station S1, j the minimum time to leave the previous
two stations must be calculated(as explained in above recursion).
Similarly, there are two ways to reach station S2, j :
Please note that the minimum times to leave stations S1, j-1 and S2, j-1 have already been
calculated.
So, we need two tables to store the partial results calculated for each station in an assembly
line. The table will be filled in bottom-up fashion.
Note:
In this post, the word “leave” has been used in place of “reach” to avoid the confusion. Since
the car chassis must spend a fixed time in each station, the word leave suits better.
Implementation:
C
339
Chapter 34. DP-34 | Assembly Line Scheduling
{
T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]);
T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]);
}
// Consider exit times and retutn minimum
return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]);
}
int main()
{
int a[][NUM_STATION] = {{4, 5, 3, 2},
{2, 10, 1, 4}};
int t[][NUM_STATION] = {{0, 7, 4, 5},
{0, 9, 2, 8}};
int e[] = {10, 12}, x[] = {18, 7};
printf("%d", carAssembly(a, t, e, x));
return 0;
}
Output:
35
Java
340
Chapter 34. DP-34 | Assembly Line Scheduling
Python3
341
Chapter 34. DP-34 | Assembly Line Scheduling
C#
342
Chapter 34. DP-34 | Assembly Line Scheduling
static int carAssembly(int [,]a, int [,]t,
int []e, int []x)
{
int []T1= new int [NUM_STATION];
int []T2 =new int[NUM_STATION] ;
int i;
// time taken to leave first station
// in line 1
T1[0] = e[0] + a[0,0];
// time taken to leave first station
// in line 2
T2[0] = e[1] + a[1,0];
// Fill tables T1[] and T2[] using
// the above given recursive relations
for (i = 1; i < NUM_STATION; ++i)
{
T1[i] = min(T1[i - 1] + a[0,i],
T2[i - 1] + t[1,i] + a[0,i]);
T2[i] = min(T2[i - 1] + a[1,i],
T1[i - 1] + t[0,i] + a[1,i]);
}
// Consider exit times and retutn
// minimum
return min(T1[NUM_STATION-1] + x[0],
T2[NUM_STATION-1] + x[1]);
}
// Driver code
public static void Main ()
{
int [,]a = { {4, 5, 3, 2},
{2, 10, 1, 4} };
int [,]t = { {0, 7, 4, 5},
{0, 9, 2, 8} };
int []e = {10, 12};
int []x = {18, 7};
Console.Write(carAssembly(a, t, e, x));
}
}
343
Chapter 34. DP-34 | Assembly Line Scheduling
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP program to find minimum
// possible time by the car chassis
// to complete
$NUM_LINE = 2;
$NUM_STATION = 4;
// Utility function to find
// minimum of two numbers
function carAssembly($a, $t,
$e, $x)
{
global $NUM_LINE,
$NUM_STATION;
$T1 = array();
$T2 = array();
$i;
$T1[0] = $e[0] + $a[0][0]; // time taken to leave
// first station in line 1
$T2[0] = $e[1] + $a[1][0]; // time taken to leave
// first station in line 2
// Fill tables T1[] and T2[]
// using the above given
// recursive relations
for ($i = 1;
$i < $NUM_STATION; ++$i)
{
$T1[$i] = min($T1[$i - 1] + $a[0][$i],
$T2[$i - 1] + $t[1][$i] +
$a[0][$i]);
$T2[$i] = min($T2[$i - 1] + $a[1][$i],
$T1[$i - 1] + $t[0][$i] +
$a[1][$i]);
}
// Consider exit times
// and return minimum
return min($T1[$NUM_STATION - 1] + $x[0],
$T2[$NUM_STATION - 1] + $x[1]);
}
344
Chapter 34. DP-34 | Assembly Line Scheduling
// Driver Code
$a = array(array(4, 5, 3, 2),
array(2, 10, 1, 4));
$t = array(array(0, 7, 4, 5),
array(0, 9, 2, 8));
$e = array(10, 12);
$x = array(18, 7);
echo carAssembly($a, $t, $e, $x);
// This code is contributed
// by anuj_67.
?>
Output:
35
The bold line shows the path covered by the car chassis for given input values.
Exercise:
Extend the above algorithm to print the path covered by the car chassis in the factory.
References:
Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest
This article is compiled by Aashish Barnwal. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Improved By : nitin mittal, vt_m
Source
https://www.geeksforgeeks.org/assembly-line-scheduling-dp-34/
345
Chapter 35
For simplicity, we have assumed that the given set is sorted. We can always add a pre-
processing step to first sort the set and then apply the below algorithms.
A simple solution is to one by one consider every pair as first two elements of AP and
check for the remaining elements in sorted set. To consider all pairs as first two elements,
we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which
linearly looks for the more elements in Arithmetic Progression (AP). This process takes
O(n3 ) time.
We can solve this problem in O(n2 ) time using Dynamic Programming. To get idea of
the DP solution, let us first discuss solution of following simpler problem.
Given a sorted set, find if there exist three elements in Arithmetic Progression
or not
Please note that, the answer is true if there are 3 or more elements in AP, otherwise false.
346
Chapter 35. DP-35 | Longest Arithmetic Progression
To find the three elements, we first fix an element as middle element and search for other
two (one smaller and one greater). We start from the second element and fix every element
as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]’
and ‘set[k]’ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1. How
to efficiently find i and k for a given j? We can find i and k in linear time using following
simple algorithm.
Following is C++ implementation of the above algorithm for the simpler problem.
347
Chapter 35. DP-35 | Longest Arithmetic Progression
To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a
fixed j. If i and k are found such that i, j, k form an AP, then the value of L[i][j] is set as
L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses
from right to left columns.
Following is the implementation of the Dynamic Programming algorithm.
C++
// C++ program to find Length of the Longest AP (llap) in a given sorted set.
// The code strictly implements the algorithm provided in the reference.
#include <iostream>
using namespace std;
// Returns length of the longest AP subset in a given set
int lenghtOfLongestAP(int set[], int n)
{
if (n <= 2) return n;
// Create a table and initialize all values as 2. The value of
// L[i][j] stores LLAP with set[i] and set[j] as first two
// elements of AP. Only valid entries are the entries where j>i
int L[n][n];
int llap = 2; // Initialize the result
// Fill entries in last column as 2. There will always be
// two elements in AP with last number of set as second
// element in AP
for (int i = 0; i < n; i++)
L[i][n-1] = 2;
// Consider every element as second element of AP
for (int j=n-2; j>=1; j--)
{
// Search for i and k for j
int i = j-1, k = j+1;
while (i >= 0 && k <= n-1)
{
if (set[i] + set[k] < 2*set[j])
k++;
// Before changing i, set L[i][j] as 2
else if (set[i] + set[k] > 2*set[j])
{ L[i][j] = 2, i--; }
else
{
// Found i and k for j, LLAP with i and j as first two
348
Chapter 35. DP-35 | Longest Arithmetic Progression
Java
349
Chapter 35. DP-35 | Longest Arithmetic Progression
350
Chapter 35. DP-35 | Longest Arithmetic Progression
351
Chapter 35. DP-35 | Longest Arithmetic Progression
Output:
4
3
5
Source
https://www.geeksforgeeks.org/longest-arithmetic-progression-dp-35/
352
Chapter 36
Input: n = 2
Output: 1 (Maximum obtainable product is 1*1)
Input: n = 3
Output: 2 (Maximum obtainable product is 1*2)
Input: n = 4
Output: 4 (Maximum obtainable product is 2*2)
Input: n = 5
Output: 6 (Maximum obtainable product is 2*3)
Input: n = 10
Output: 36 (Maximum obtainable product is 3*3*4)
1) Optimal Substructure:
This problem is similar to Rod Cutting Problem. We can get the maximum product by
making a cut at different positions and comparing the values obtained after a cut. We can
recursively call the same function for a piece obtained after a cut.
Let maxProd(n) be the maximum product for a rope of length n. maxProd(n) can be
written as following.
353
Chapter 36. DP-36 | Maximum Product Cutting
C++
Java
354
Chapter 36. DP-36 | Maximum Product Cutting
Python3
355
Chapter 36. DP-36 | Maximum Product Cutting
# Driver program to test above functions
print("Maximum Product is ", maxProd(10));
# This cide is contributed
# by Sumit Sudhakar
C#
356
Chapter 36. DP-36 | Maximum Product Cutting
Output:
Maximum Product is 36
Considering the above implementation, following is recursion tree for a Rope of length 5.
In the above partial recursion tree, mP(3) is being solved twice. We can see that there
are many subproblems which are solved again and again. Since same suproblems are called
again, this problem has Overlapping Subprolems property. So the problem has both prop-
erties (see thisand this) of a dynamic programming problem. Like other typical Dynamic
Programming(DP) problems, recomputations of same subproblems can be avoided by con-
structing a temporary array val[] in bottom up manner.
357
Chapter 36. DP-36 | Maximum Product Cutting
val[i] = max_val;
}
return val[n];
}
Time Complexity of the Dynamic Programming solution is O(n^2) and it requires O(n)
extra space.
A Tricky Solution:
If we see some examples of this problems, we can easily observe following pattern.
The maximum product can be obtained be repeatedly cutting parts of size 3 while size
is greater than 4, keeping the last part as size of 2 or 3 or 4. For example, n = 10, the
maximum product is obtained by 3, 3, 4. For n = 11, the maximum product is obtained
by 3, 3, 3, 2. Following is the implementation of this approach.
C++
#include <iostream>
using namespace std;
/* The main function that teturns the max possible product */
int maxProd(int n)
{
// n equals to 2 or 3 must be handled explicitly
if (n == 2 || n == 3) return (n-1);
// Keep removing parts of size 3 while n is greater than 4
int res = 1;
while (n > 4)
{
n -= 3;
res *= 3; // Keep multiplying 3 to res
}
return (n * res); // The last part multiplied by previous parts
}
/* Driver program to test above functions */
int main()
{
cout << "Maximum Product is " << maxProd(10);
return 0;
}
Java
358
Chapter 36. DP-36 | Maximum Product Cutting
class GFG {
/* The main function that returns the
max possible product */
static int maxProd(int n)
{
// n equals to 2 or 3 must be handled
// explicitly
if (n == 2 || n == 3) return (n-1);
// Keep removing parts of size 3
// while n is greater than 4
int res = 1;
while (n > 4)
{
n -= 3;
// Keep multiplying 3 to res
res *= 3;
}
// The last part multiplied by
// previous parts
return (n * res);
}
/* Driver program to test above functions */
public static void main(String[] args)
{
System.out.println("Maximum Product is "
+ maxProd(10));
}
}
// This code is contributed by Prerna Saini
Python3
359
Chapter 36. DP-36 | Maximum Product Cutting
# Keep removing parts of size 3
# while n is greater than 4
res = 1
while (n > 4):
n -= 3;
# Keep multiplying 3 to res
res *= 3;
# The last part multiplied
# by previous parts
return (n * res)
# Driver program to test above functions
print("Maximum Product is ", maxProd(10));
# This code is contributed
# by Sumit Sudhakar
C#
360
Chapter 36. DP-36 | Maximum Product Cutting
PHP
<?php
/* The main function that returns
the max possible product */
function maxProd($n)
{
// n equals to 2 or 3 must
// be handled explicitly
if ($n == 2 || $n == 3)
return ($n - 1);
// Keep removing parts of size
// 3 while n is greater than 4
$res = 1;
while ($n > 4)
{
$n = $n - 3;
// Keep multiplying 3 to res
$res = $res * 3;
}
// The last part multiplied
// by previous parts
return ($n * $res);
}
// Driver code
echo ("Maximum Product is ");
echo(maxProd(10));
// This code is contributed
// by Shivi_Aggarwal
?>
361
Chapter 36. DP-36 | Maximum Product Cutting
Output:
Maximum Product is 36
Improved By : Shivi_Aggarwal
Source
https://www.geeksforgeeks.org/maximum-product-cutting-dp-36/
362
Chapter 37
DP-37 | Boolean
Parenthesization Problem
Symbols
'T' ---> true
'F' ---> false
Operators
& ---> boolean AND
| ---> boolean OR
^ ---> boolean XOR
Count the number of ways we can parenthesize the expression so that the value of expression
evaluates to true.
Let the input be in form of two arrays one contains the symbols (T and F) in order and
other contains operators (&, | and ^}
Examples:
363
Chapter 37. DP-37 | Boolean Parenthesization Problem
Solution:
Let T(i, j) represents the number of ways to parenthesize the symbols between i and j
(both inclusive) such that the subexpression between i and j evaluates to true.
Let F(i, j) represents the number of ways to parenthesize the symbols between i and j (both
inclusive) such that the subexpression between i and j evaluates to false.
Base Cases:
364
Chapter 37. DP-37 | Boolean Parenthesization Problem
If we draw recursion tree of above recursive solution, we can observe that it many overlapping
subproblems. Like other dynamic programming problems, it can be solved by filling a table
in bottom up manner. Following is C++ implementation of dynamic programming solution.
#include<iostream>
#include<cstring>
using namespace std;
// Returns count of all possible parenthesizations that lead to
// result true for a boolean expression with symbols like true
// and false and operators like &, | and ^ filled between symbols
int countParenth(char symb[], char oper[], int n)
{
int F[n][n], T[n][n];
// Fill diaginal entries first
// All diagonal entries in T[i][i] are 1 if symbol[i]
// is T (true). Similarly, all F[i][i] entries are 1 if
// symbol[i] is F (False)
for (int i = 0; i < n; i++)
{
F[i][i] = (symb[i] == 'F')? 1: 0;
T[i][i] = (symb[i] == 'T')? 1: 0;
}
// Now fill T[i][i+1], T[i][i+2], T[i][i+3]... in order
// And F[i][i+1], F[i][i+2], F[i][i+3]... in order
for (int gap=1; gap<n; ++gap)
{
for (int i=0, j=gap; j<n; ++i, ++j)
{
T[i][j] = F[i][j] = 0;
for (int g=0; g<gap; g++)
{
// Find place of parenthesization using current value
// of gap
int k = i + g;
// Store Total[i][k] and Total[k+1][j]
int tik = T[i][k] + F[i][k];
int tkj = T[k+1][j] + F[k+1][j];
// Follow the recursive formulas according to the current
// operator
if (oper[k] == '&')
{
T[i][j] += T[i][k]*T[k+1][j];
F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]);
365
Chapter 37. DP-37 | Boolean Parenthesization Problem
}
if (oper[k] == '|')
{
F[i][j] += F[i][k]*F[k+1][j];
T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]);
}
if (oper[k] == '^')
{
T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];
F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];
}
}
}
}
return T[0][n-1];
}
// Driver program to test above function
int main()
{
char symbols[] = "TTFT";
char operators[] = "|&^";
int n = strlen(symbols);
// There are 4 ways
// ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T))
cout << countParenth(symbols, operators, n);
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/
366
Chapter 38
Input : W = 10, n = 3
val[] = {7, 8, 4}
wt[] = {3, 8, 6}
Output: 11
We get maximum value by picking items of 3 KG and 6 KG.
We have discussed a Dynamic Programming based solution here. In the previous solution, we
used a n * W matrix. We can reduce the used extra space. The idea behind the optimization
is, to compute mat[i][j], we only need solution of previous row. In 0-1 Knapsack Problem if
we are currently on mat[i][j] and we include ith element then we move j-wt[i] steps back in
previous row and if we exclude the current element we move on jth column in previous row.
So here we can observe that at a time we are working only with 2 consecutive rows.
In below solution, we create a matrix of size 2*W. If n is odd, then final answer will be at
mat[0][W] and if n is even then final answer will be at mat[1][W] because index starts from
0.
367
Chapter 38. A Space Optimized DP solution for 0-1 Knapsack Problem
368
Chapter 38. A Space Optimized DP solution for 0-1 Knapsack Problem
mat[0][j] = mat[1][j];
}
}
i++;
}
// Return mat[0][W] if n is odd, else mat[1][W]
return (n%2 != 0)? mat[0][W] : mat[1][W];
}
// Driver program to test the cases
int main()
{
int val[] = {7, 8, 4}, wt[] = {3, 8, 6}, W = 10, n = 3;
cout << KnapSack(val, wt, n, W) << endl;
return 0;
}
Output:
11
369
Chapter 38. A Space Optimized DP solution for 0-1 Knapsack Problem
Output:
11
Source
https://www.geeksforgeeks.org/space-optimized-dp-solution-0-1-knapsack-problem/
370
Chapter 39
371
Chapter 39. A Space Optimized Solution of LCS
We strongly recommend that you click here and practice it, before moving on
to the solution.
One important observation in above simple implementation is, in each iteration of outer
loop we only, need values from all columns of previous row. So there is no need of
storing all rows in our DP matrix, we can just store two rows at a time and use them, in that
way used space will reduce from L[m+1][n+1] to L[2][n+1]. Below is the implementation
of above idea.
C++
372
Chapter 39. A Space Optimized Solution of LCS
bi = i & 1;
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[bi][j] = 0;
else if (X[i-1] == Y[j-1])
L[bi][j] = L[1 - bi][j - 1] + 1;
else
L[bi][j] = max(L[1 - bi][j],
L[bi][j - 1]);
}
}
// Last filled entry contains
// length of LCS
// for X[0..n-1] and Y[0..m-1]
return L[bi][n];
}
// Driver code
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
printf("Length of LCS is %d\n", lcs(X, Y));
return 0;
}
Java
373
Chapter 39. A Space Optimized Solution of LCS
374
Chapter 39. A Space Optimized Solution of LCS
Python3
C#
375
Chapter 39. A Space Optimized Solution of LCS
376
Chapter 39. A Space Optimized Solution of LCS
Output:
Length of LCS is 4
Source
https://www.geeksforgeeks.org/space-optimized-solution-lcs/
377
Chapter 40
We can solve this problem by parenthesizing all possible valid substring of the expression
and then evaluating them, but as we can see that it will involve solving lots of repeating
subproblem, to save ourselves we can follow a dynamic programming approach.
We store the result for each substring in a map and if string in recursion is already solved,
we return result from map instead of solving that again.
Below code runs a loop in the string and if at any instant, character is operator then we
divide the input from there, recursively solve each part and then combine the result in all
possible ways.
See the use of c_str() function, this function converts the C++ string into C char array,
378
Chapter 40. All ways to add parenthesis for evaluation
this function is used in below code because atoi() function expects a character array as an
argument not the string. It converts character array to number.
379
Chapter 40. All ways to add parenthesis for evaluation
}
}
// if input contains only number then save that
// into res vector
if (res.size() == 0)
res.push_back(atoi(input.c_str()));
// Store in memo so that input string is not
// processed repeatedly
memo[input] = res;
return res;
}
// method to return all possible output
// from input expression
vector<int> possibleResult(string input)
{
map< string, vector<int> > memo;
return possibleResultUtil(input, memo);
}
// Driver code to test above methods
int main()
{
string input = "5*4-3*2";
vector<int> res = possibleResult(input);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
return 0;
}
Output:
-10 10 14 10 34
Source
https://www.geeksforgeeks.org/all-ways-to-add-parenthesis-for-evaluation/
380
Chapter 41
Input : N = 7
Output : 0 1 3 8
Input : N = 15
Output : 0 1 3 8 21 55 144 377
Source
https://www.geeksforgeeks.org/alternate-fibonacci-numbers/
C++
381
Chapter 41. Alternate Fibonacci Numbers
/* 0th and 1st number of the series are 0 and 1*/
int f1 = 0;
int f2 = 1;
cout << f1 << " ";
for (int i = 2; i <= n; i++) {
int f3 = f2 + f1;
if (i % 2 == 0)
cout << f3 << " ";
f1 = f2;
f2 = f3;
}
}
int main()
{
int N = 15;
alternateFib(N);
return 0;
}
Java
382
Chapter 41. Alternate Fibonacci Numbers
C#
// Alternate Fibonacci Series
// using Dynamic Programming
using System;
class GFG
{
static void alternateFib(int n)
{
if (n < 0) return; /* 0th and 1st number of the series are 0 and 1*/ int f1 = 0; int f2 = 1;
Console.Write(f1 + ” ”); for (int i = 2; i <= n; i++) { int f3 = f2 + f1; if (i % 2 == 0)
Console.Write(f3 + ” ”); f1 = f2; f2 = f3; } } // Driver Code public static void Main () { int
N = 15; alternateFib(N); } } // This code is contributed // by chandan_jnu. [tabbyending]
Output:
0 1 3 8 21 55 144 377
383
Chapter 42
Balanced expressions such that given positions have opening brackets - GeeksforGeeks
Given an integer n and an array of positions ‘position[]’ (1 <= position[i] <= 2n), find the
number of ways of proper bracket expressions that can be formed of length 2n such that
given positions have opening bracket. Examples :
384
Chapter 42. Balanced expressions such that given positions have opening brackets
The base case of the DP is, DP0, 0 =1. We need to fill the first position with a ‘[‘ bracket,
and there is only way to do this.
If the position has a opening bracket sequence which can be marked by a hash array,
then the recurrence occurs as :
385
Chapter 42. Balanced expressions such that given positions have opening brackets
// iterate and formulate the recurrences
for (int i = 1; i <= 2 * n; i++) {
for (int j = 0; j <= 2 * n; j++) {
// if position has a opening bracket
if (h[i]) {
if (j != 0)
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 0;
}
else {
if (j != 0)
dp[i][j] = dp[i - 1][j - 1] +
dp[i - 1][j + 1];
else
dp[i][j] = dp[i - 1][j + 1];
}
}
}
// return answer
return dp[2 * n][0];
}
// driver code
int main()
{
int n = 3;
// positions where opening braces
// will be placed
int pos[] = { 2 };
int k = sizeof(pos)/sizeof(pos[0]);
cout << arrangeBraces(n, pos, k);
return 0;
}
Output :
386
Chapter 42. Balanced expressions such that given positions have opening brackets
Source
https://www.geeksforgeeks.org/balanced-expressions-such-that-given-positions-have-opening-brackets/
387
Chapter 43
Balanced expressions such that given positions have opening brackets | Set 2 - GeeksforGeeks
Given an integer n and an array of positions ‘position[]’ (1 <= length(position[]) <= 2n),
find the number of ways of proper bracket expressions that can be formed of length 2n such
that given positions have the opening bracket.
Note: position[] array is given in the form of (1-based indexing) [0, 1, 1, 0]. Here 1
denotes the positions at which open bracket should be placed. At positions with value 0,
either of opening and closing bracket can be placed.
Examples:
Dynamic Programming approach of this problem has been already discussed here. In this
post, recursive and recursion using memoization approach will be discussed.
Algorithm–
388
Chapter 43. Balanced expressions such that given positions have opening brackets | Set 2
1. Mark all the positions with open brackets in the given array adj as 1.
2. Run a recursive loop, such that –
• If count of total brackets(opening brackets subracted from closing brackets is less
than zero), return 0.
• If the index reaches till n and if the total brackets=0, then a solution is obtained
and return 1, otherwise return 0.
• If the index has 1 pre-assigned to it, return the function recursively with index+1
and increment the total brackets.
• Otherwise Return the function recursively by inserting open brackets at that
index and incrementing total brackets by 1 + inserting closed brackets at that
index and decrementing total brackets by 1 and move on to the next index till n.
389
Chapter 43. Balanced expressions such that given positions have opening brackets | Set 2
Output:
Memoized Approach: Time complexity of the above algorithm can be optimized by using
Memorization. The only thing to be done is to use an array to store the results of previous
iterations so that there is no need to recursively call the same function more than once, if
the value is already calculated.
Below is the required implementation:
390
Chapter 43. Balanced expressions such that given positions have opening brackets | Set 2
// If index reaches the end of expression
if (index == n) {
// If brackets are balanced
if (openbrk == 0)
return 1;
else
return 0;
}
// If already stored in dp
if (dp[index][openbrk] != -1)
return dp[index][openbrk];
// If the current index has assigned open bracket
if (adj[index] == 1) {
// Move forward increasing the
// length of open brackets
dp[index][openbrk] = find(index + 1,
openbrk + 1, n, dp, adj);
}
else {
// Move forward by inserting open as
// well as closed brackets on that index
dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj)
+ find(index + 1, openbrk - 1, n, dp, adj);
}
// return the answer
return dp[index][openbrk];
}
// Driver Code
int main()
{
// DP array to precompute the answer
int dp[N][N];
int n = 2;
memset(dp, -1, sizeof(dp));
// Open brackets at postion 1
int adj[4] = { 1, 0, 0, 0 };
// Calling the find function to calculate the answer
cout << find(0, 0, 2 * n, dp, adj) << endl;
391
Chapter 43. Balanced expressions such that given positions have opening brackets | Set 2
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/balanced-expressions-such-that-given-positions-have-opening-brackets-set-2/
392
Chapter 44
Input: n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
{ {1}, {2} }
{ {1, 2} }
Input: n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
{ {1}, {2}, {3} }
{ {1}, {2, 3} }
{ {2}, {1, 3} }
{ {3}, {1, 2} }
{ {1, 2, 3} }.
Value of S(n, k) can be defined recursively as, S(n+1, k) = k*S(n, k) + S(n, k-1)
393
Chapter 44. Bell Numbers (Number of ways to Partition a Set)
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
Interpretation
Then Bell(n, k) counts the number of partitions of the set {1, 2, …, n + 1} in which the
element k + 1 is the largest element that can be alone in its set.
For example, Bell(3, 2) is 3, it is count of number of partitions of {1, 2, 3, 4} in which 3 is
the largest singleton element. There are three such partitions:
394
Chapter 44. Bell Numbers (Number of ways to Partition a Set)
C++
Java
395
Chapter 44. Bell Numbers (Number of ways to Partition a Set)
{
// Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for (int j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
// Driver program
public static void main (String[] args)
{
for (int n=0; n<=5; n++)
System.out.println("Bell Number "+ n +
" is "+bellNumber(n));
}
}
// This code is contributed by Pramod Kumar
Python3
396
Chapter 44. Bell Numbers (Number of ways to Partition a Set)
C#
PHP
<?php
// A PHP program to find
// n'th Bell number
397
Chapter 44. Bell Numbers (Number of ways to Partition a Set)
Output:
Bell Number 0 is 1
Bell Number 1 is 1
Bell Number 2 is 2
Bell Number 3 is 5
Bell Number 4 is 15
Bell Number 5 is 52
Time Complexity of above solution is O(n2 ). We will soon be discussing other more efficient
methods of computing Bell Numbers.
Another problem that can be solved by Bell Numbers.
A number is squarefree if it is not divisible by a perfect square other than 1. For example,
6 is a square free number but 12 is not as it is divisible by 4.
Given a squarefree number x, find the number of different multiplicative partitions of x. The
number of multiplicative partitions is Bell(n) where n is number of prime factors of x. For
398
Chapter 44. Bell Numbers (Number of ways to Partition a Set)
example x = 30, there are 3 prime factors of 2, 3 and 5. So the answer is Bell(3) which is 5.
The 5 partitions are 1 x 30, 2 x15, 3 x 10, 5 x 6 and 2 x 3 x 5.
Exercise:
The above implementation causes arithmetic overflow for slightly larger values of n. Ex-
tend the above program so that results are computed under modulo 1000000007 to avoid
overflows.
Reference:
https://en.wikipedia.org/wiki/Bell_number
https://en.wikipedia.org/wiki/Bell_triangle
This article is contributed by Rajeev Agrawal. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above.
Improved By : nitin mittal, jit_t
Source
https://www.geeksforgeeks.org/bell-numbers-number-of-ways-to-partition-a-set/
399
Chapter 45
Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every
person) - GeeksforGeeks
Consider the below problems statement.
There are 100 different types of caps each having a unique id from 1 to 100. Also, there
are ‘n’ persons each having a collection of a variable number of caps. One day all of these
persons decide to go in a party wearing a cap but to look unique they decided that none of
them will wear the same type of cap. So, count the total number of arrangements or ways
such that none of them is wearing the same type of cap.
Constraints: 1 <= n <= 10 Example:
The first line contains the value of n, next n lines contain collections
of all the n persons.
Input:
3
5 100 1 // Collection of the first person.
2 // Collection of the second person.
5 100 // Collection of the third person.
Output:
4
Explanation: All valid possible ways are (5, 2, 100), (100, 2, 5),
(1, 2, 5) and (1, 2, 100)
400
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
Let i be the current cap number (caps from 1 to i-1 are already
processed). Let integer variable mask indicates that the persons w
earing and not wearing caps. If i'th bit is set in mask, then
i'th person is wearing a cap, else not.
401
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
Note that the expression "mask | (1 << j)" sets j'th bit in mask.
And a person can wear cap i if it is there in the person's cap list
provided as input.
If we draw the complete recursion tree, we can observe that many subproblems are solved
again and again. So we use Dynamic Programming. A table dp[][] is used such that in every
entry dp[i][j], i is mask and j is cap number.
Since we want to access all persons that can wear a given cap, we use an array of vectors,
capList[101]. A value capList[i] indicates the list of persons that can wear cap i.
Below is the implementation of above idea.
C/C++
402
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
// If not everyone is wearing a cap and also there are no more
// caps left to process, so there is no way, thus return 0;
if (i > 100) return 0;
// If we already have solved this subproblem, return the answer.
if (dp[mask][i] != -1) return dp[mask][i];
// Ways, when we don't include this cap in our arrangement
// or solution set.
long long int ways = countWaysUtil(mask, i+1);
// size is the total number of persons having cap with id i.
int size = capList[i].size();
// So, assign one by one ith cap to all the possible persons
// and recur for remaining caps.
for (int j = 0; j < size; j++)
{
// if person capList[i][j] is already wearing a cap so continue as
// we cannot assign him this cap
if (mask & (1 << capList[i][j])) continue;
// Else assign him this cap and recur for remaining caps with
// new updated mask vector
else ways += countWaysUtil(mask | (1 << capList[i][j]), i+1);
ways %= MOD;
}
// Save the result and return it.
return dp[mask][i] = ways;
}
// Reads n lines from standard input for current test case
void countWays(int n)
{
//----------- READ INPUT --------------------------
string temp, str;
int x;
getline(cin, str); // to get rid of newline character
for (int i=0; i<n; i++)
{
getline(cin, str);
stringstream ss(str);
// while there are words in the streamobject ss
while (ss >> temp)
{
403
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
stringstream s;
s << temp;
s >> x;
// add the ith person in the list of cap if with id x
capList[x].push_back(i);
}
}
//----------------------------------------------------
// All mask is used to check whether all persons
// are included or not, set all n bits as 1
allmask = (1 << n) - 1;
// Initialize all entries in dp as -1
memset(dp, -1, sizeof dp);
// Call recursive function count ways
cout << countWaysUtil(0, 1) << endl;
}
// Driver Program
int main()
{
int n; // number of persons in every test case
cin >> n;
countWays(n);
return 0;
}
Java
404
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
405
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
// Save the result and return it.
return dp[mask][i] = (int) ways;
}
// Reads n lines from standard input for current test case
static void countWays(int n) throws Exception
{
//----------- READ INPUT --------------------------
String str;
String split[];
int x;
for (int i=0; i<n; i++)
{
str = br.readLine();
split = str.split(" ");
// while there are words in the split[]
for (int j = 0; j < split.length; j++) {
// add the ith person in the list of cap if with id x
x = Integer.parseInt(split[j]);
capList[x].add(i);
}
}
//----------------------------------------------------
// All mask is used to check of all persons
// are included or not, set all n bits as 1
allmask = (1 << n) - 1;
// Initialize all entries in dp as -1
for (int[] is : dp) {
for (int i = 0; i < is.length; i++) {
is[i] = -1;
}
}
// Call recursive function count ways
System.out.println(countWaysUtil(0, 1));
}
// Driver method
public static void main(String args[]) throws Exception
{
int n; // number of persons in every test case
406
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
Python
407
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
# assign ith cap one by one to all the possible persons
# and recur for remaining caps.
if cap_no in self.caps:
for ppl in self.caps[cap_no]:
# if person 'ppl' is already wearing a cap then continue
if mask & (1 << ppl) : continue
# Else assign him this cap and recur for remaining caps with
# new updated mask vector
ways += self.countWaysUtil(dp, mask | (1 << ppl), cap_no + 1)
ways = ways % (10**9 + 7)
# Save the result and return it
dp[mask][cap_no] = ways
return dp[mask][cap_no]
def countWays(self,N):
# Reads n lines from standard input for current test case
# create dictionary for cap. cap[i] = list of person having
# cap no i
for ppl in range(N):
cap_possessed_by_person = map(int, raw_input().strip().split())
for i in cap_possessed_by_person:
self.caps[i].append(ppl)
# allmask is used to check if all persons
# are included or not, set all n bits as 1
self.allmask = (1 << N) -1
# Initialize all entries in dp as -1
dp = [[-1 for j in range(self.total_caps + 1)] for i in range(2 ** N)]
# Call recursive function countWaysUtil
# result will be in dp[0][1]
print self.countWaysUtil(dp, 0, 1,)
#Driver Program
408
Chapter 45. Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique
cap to every person)
def main():
No_of_people = input() # number of persons in every test case
AssignCap().countWays(No_of_people)
if __name__ == '__main__':
main()
# This code is contributed by Neelam Yadav
Input:
3
5 100 1
2
5 100
Output:
This article is contributed by Gaurav Ahirwar. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Source
https://www.geeksforgeeks.org/bitmasking-and-dynamic-programming-set-1-count-ways-to-assign-unique-cap-to-ev
409
Chapter 46
Problem Description:
410
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
The first part is to calculate the minimum distance between the two cells. We can do it by
simply using a BFS as all the distances are unit distance. To optimize our solution we will
be pre-calculating the distances taking the initial location and the location of the houses as
the source point for our BFS.
Each BFS traversal takes O(size of grid) time. Therefore, it is O(X * size_of_grid) for
overall pre-calculation, where X = number of houses + 1 (initial position)
Now lets’s think of a DP state
So we will be needing to track the visited houses and the last visited house to uniquely
identify a state in this problem.
Therefore, we will be taking dp[index][mask] as our DP state.
Here,
index : tells us the location of current house
mask : tells us the houses that are visited ( if ith bit is set in mask then this means that
the ith dirty tile is cleaned)
Whereas dp[index][mask] will tell us the minimum distance to visit X(number of set bits in
mask) houses corresponding to their order of their occurrence in the mask where the last
visited house is house at location index.
State transition relation
So our initial state will be dp[0][0] this tells that we are currently at initial tile that is our
initial location and mask is 0 that states that no house is visited till now.
And our final destination state will be dp[any index][LIMIT_MASK], here
LIMIT_MASK = (1<<N) – 1
and N = number of houses.
Therefore our DP state transition can be stated as
dp(curr_idx)(curr_mask) = min{
for idx : off_bits_in_curr_mask
dp(idx)(cur_mask.set_bit(idx)) + dist[curr_idx][idx]
}
The above relation can be visualized as the minimum distance to visit all the houses by
standing at curr_idx house and by already visiting cur_mask houses is equal to min of
distance between the curr_idx house and idx house + minimum distance to visit all the
houses by standing at idx house and by already
visiting ( cur_mask | (1 <<idx) ) houses.
So, here we iterate over all possible idx values such that cur_mask has ith bit as 0 that tells
us that ith house is not visited.
Whenever we have our mask = LIMIT_MASK, this means that we have visited all the
houses in the town. So, we will add the distance from the last visited town (i.e the town at
cur_idx positon) to the initial position (0, 0).
The C++ program for the above implementation is given below:
411
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
#include <bits/stdc++.h>
using namespace std;
#define INF 99999999
#define MAXR 12
#define MAXC 12
#define MAXMASK 2048
#define MAXHOUSE 12
// stores distance taking souce
// as every dirty tile
int dist[MAXR][MAXC][MAXHOUSE];
// memoization for dp states
int dp[MAXHOUSE][MAXMASK];
// stores coordinates for
// dirty tiles
vector < pair < int, int > > dirty;
// Directions
int X[] = {-1, 0, 0, 1};
int Y[] = {0, 1, -1, 0};
char arr[21][21];
// len : number of dirty tiles + 1
// limit : 2 ^ len -1
// r, c : number of rows and columns
int len, limit, r, c;
// Returns true if current position
// is safe to visit
// else returns false
// Time Complexity : O(1)
bool safe(int x, int y)
{
if (x >= r or y>= c or x<0 or y<0)
return false;
if (arr[x][y] == '#')
return false;
return true;
}
// runs BFS traversal at tile idx
// calulates distance to every cell
412
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
// in the grid
// Time Complexity : O(r*c)
void getDist(int idx){
// visited array to track visited cells
bool vis[21][21];
memset(vis, false, sizeof(vis));
// getting current positon
int cx = dirty[idx].first;
int cy = dirty[idx].second;
// initializing queue for bfs
queue < pair < int, int > > pq;
pq.push({cx, cy});
// initializing the dist to max
// because some cells cannot be visited
// by taking source cell as idx
for (int i = 0;i<= r;i++)
for (int j = 0;j<= c;j++)
dist[i][j][idx] = INF;
// base conditions
vis[cx][cy] = true;
dist[cx][cy][idx] = 0;
while (! pq.empty())
{
auto x = pq.front();
pq.pop();
for (int i = 0;i<4;i++)
{
cx = x.first + X[i];
cy = x.second + Y[i];
if (safe(cx, cy))
{
if (vis[cx][cy])
continue;
vis[cx][cy] = true;
dist[cx][cy][idx] = dist[x.first][x.second][idx] + 1;
pq.push({cx, cy});
}
}
}
}
// Dynamic Programming state transition recursion
413
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
414
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
415
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
// ...#...
// ...#.*.
// ...#...
// .*.#.*.
// ...#...
char Arr[5][7] = { {'.', '.', '.', '#', '.', '.', '.'},
{'.', '.', '.', '#', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'},
{'.', '*', '.', '#', '.', '*', '.'},
{'.', '.', '.', '#', '.', '.', '.'}
};
r = 5; c = 7;
cout << "The given grid : " << endl;
for (int i = 0;i<r;i++)
{
for (int j = 0;j<c;j++)
{
cout << Arr[i][j] << " ";
arr[i][j] = Arr[i][j];
}
cout << endl;
}
// - initializitiation
// - precalculations
init();
ans = solve(0, 1);
cout << "Minimum distance for the given grid : ";
if (ans >= INF)
cout << "not possible" << endl;
else
cout << ans << endl;
return 0;
}
Output:
416
Chapter 46. Bitmasking and Dynamic Programming | Set-2 (TSP)
Note:
We have used the initial state to be dp[0][1] because we have pushed the start location at
the first position in the container of houses. Hence, our Bit Mask will be 1 as the 0th bit is
set i.e we have visited the starting location for our trip.
Time Complexity:
Consider the number of houses to be n. So, there are n * (2n ) states and at every state,
we are looping over n houses to transit over to next state and because of memoization we
are doing this looping transition only once for each state. Therefore, our Time Complexity
is O(n2 * 2n ).
Recommended:
• http://www.spoj.com/problems/CLEANRBT/
• https://www.youtube.com/watch?v=-JjA4BLQyqE
Source
https://www.geeksforgeeks.org/bitmasking-dynamic-programming-set-2-tsp/
417
Chapter 47
Approach :
A simple solution is to do BFS or DFS to find if there is a path.
A better solution is to mark all accessible nodes by changing their value to 1. First change
the value of first top left element value to 1 then in the first row get previous value and set
to current index in only first row if the value is -1 then no change then in first column do
the same.
418
Chapter 47. Check for possible path in 2D matrix
Then start from first row and first column and take previous row value and previous row
column and find max between them, and set to current index, if current index value is -1
then no change.
At the end if right bottom is 1 then return yes else return no.
C++
419
Chapter 47. Check for possible path in 2D matrix
Java
420
Chapter 47. Check for possible path in 2D matrix
}
//Driver code
public static void main(String[] args)
{
// Given array
int arr[][] = { { 0, 0, 0, -1, 0 },
{ -1, 0, 0, -1, -1 },
{ 0, 0, 0, -1, 0 },
{ -1, 0, -1, 0, -1 },
{ 0, 0, -1, 0, 0 } };
// path from arr[0][0]
// to arr[row][col]
if (isPath(arr))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed
// by prerna saini
C#
421
Chapter 47. Check for possible path in 2D matrix
PHP
<?php
// PHP program to find if
// there is path from top
// left to right bottom
$row = 5;
$col = 5;
// to find the path from
// top left to bottom right
function isPath($arr)
{
global $row, $col;
422
Chapter 47. Check for possible path in 2D matrix
$arr[0][0] = 1;
// Mark reachable (from
// top left) nodes in
// first row and first column.
for ($i = 1; $i < $row; $i++)
if ($arr[0][$i] != -1)
$arr[0][$i] = $arr[0][$i - 1];
for ($j = 1; $j < $col; $j++)
if ($arr[$j][0] != -1)
$arr[$j][0] = $arr[$j - 1][0];
// Mark reachable nodes
// in remaining matrix.
for ($i = 1; $i < $row; $i++)
for ($j = 1; $j < $col; $j++)
if ($arr[$i][$j] != -1)
$arr[$i][$j] = max($arr[$i][$j - 1],
$arr[$i - 1][$j]);
// return yes if right
// bottom index is 1
return ($arr[$row - 1][$col - 1] == 1);
}
// Driver Code
// Given array
$arr = array(array(0, 0, 0, 1, 0),
array(-1, 0, 0, -1, -1),
array(0, 0, 0, -1, 0),
array(-1, 0, -1, 0, -1),
array(0, 0, -1, 0, 0));
// path from arr[0][0]
// to arr[row][col]
if (isPath($arr))
echo "Yes";
else
echo "No";
// This code is contributed by anuj_67.
?>
Output:
423
Chapter 47. Check for possible path in 2D matrix
No
Source
https://www.geeksforgeeks.org/check-possible-path-2d-matrix/
424
Chapter 48
Input : n = 3, x = 4
a[] = {2, 4, 2}
Output : YES
There are n = 3 persons say and maximum
allowed time is x = 4 units. Let the persons
be P0, P1 and P2 and two machines be M0 and M1.
At t0 : P0 goes to M0
At t0 : P2 goes to M1
At t2 : M0 is free, p3 goes to M0
At t4 : both M0 and M1 are free and all 3 have
given their vote.
Let sum be the total time taken by all n people. If sum <=x, then answer will obviously
be YES. Otherwise, we need to check whether the given array can be split in two parts
such that sum of first part and sum of second part are both less than or equal to x. The
problem is similar to the knapsack problem. Imagine two knapsacks each with capacity x.
Now find, maximum people who can vote on any one machine i.e. find maximum subset
sum for knapsack of capacity x. Let this sum be s1. Now if (sum-s1) <= x, then answer is
YES else answer is NO.
425
Chapter 48. Check if all people can vote on two machines
Output:
426
Chapter 48. Check if all people can vote on two machines
YES
Source
https://www.geeksforgeeks.org/check-people-can-vote-two-machines/
427
Chapter 49
A simple solution is to recursively consider all possible scenarios ie either use a ;+’ or a ‘-‘
operator between the elements and maintain a variable sum which stores the result.If this
result is divisible by M then return true else return false
Recursive implementation is as follows:
428
Chapter 49. Check if any valid sequence is divisible by M
if (index == n) {
// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// recursively call by considering '+'
// or '-' between index and index+1
// 1.Try placing '+'
bool placeAdd = isPossible(index + 1,
sum + arr[index]);
// 2. Try placing '-'
bool placeMinus = isPossible(index + 1,
sum - arr[index]);
if (placeAdd || placeMinus)
return true;
return false;
}
There are overlapping subproblems as shown in the image below (Note: the image represents
the recursion tree till index = 3)
429
Chapter 49. Check if any valid sequence is divisible by M
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
bool isPossible(int n, int index, int sum,
int M, int arr[], int dp[][MAX])
{
// Base case
if (index == n) {
// check if sum is divisible by M
430
Chapter 49. Check if any valid sequence is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// check if the current state
// is already computed
if (dp[index][sum] != -1)
return dp[index][sum];
// 1.Try placing '+'
bool placeAdd = isPossible(n, index + 1,
sum + arr[index], M, arr, dp);
// 2. Try placing '-'
bool placeMinus = isPossible(n, index + 1,
sum - arr[index], M, arr, dp);
// calculate value of res for recursive case
bool res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
dp[index][sum] = res;
return res;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
int M = 4;
int dp[n + 1][MAX];
memset(dp, -1, sizeof(dp));
bool res;
res = isPossible(n, 0, 0, M, arr, dp);
cout << (res ? "True" : "False") << endl;
return 0;
}
Output:
True
The Complexity of this method is O(N*sum) where sum is the maximum possible sum for
431
Chapter 49. Check if any valid sequence is divisible by M
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int isPossible(int n, int index, int modulo,
int M, int arr[], int dp[][MAX])
{
// Calculate modulo for this call
modulo = ((modulo % M) + M) % M;
// Base case
if (index == n) {
// check if sum is divisible by M
if (modulo == 0)
return 1;
return 0;
}
// check if the current state is
// already computed
if (dp[index][modulo] != -1)
return dp[index][modulo];
// 1.Try placing '+'
int placeAdd = isPossible(n, index + 1,
modulo + arr[index], M, arr, dp);
// 2. Try placing '-'
int placeMinus = isPossible(n, index + 1,
modulo - arr[index], M, arr, dp);
// calculate value of res for recursive
// case
bool res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
432
Chapter 49. Check if any valid sequence is divisible by M
dp[index][modulo] = res;
return res;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
int M = 4;
// MAX is the Maximum value M can take
int dp[n + 1][MAX];
memset(dp, -1, sizeof(dp));
bool res;
res = isPossible(n, 1, arr[0], M, arr, dp);
cout << (res ? "True" : "False") << endl;
return 0;
}
Output:
True
Source
https://www.geeksforgeeks.org/check-valid-sequence-divisible-m/
433
Chapter 50
Input : N = 3, K = 2
A[] = { 1, 1, 1 }
Output : Yes
Explanation
Replace index 0 element with -1. It will sum of array equal to k = 2.
Input : N = 4, K = 5
A[] = { 1, 2, 3, 4 }
Output : Yes
434
Chapter 50. Check if array sum can be made K by three operations on it
Also, it is possible that the intermediate sum of the array is negative, in that case do not
perform any operation and ignore it thus letting the sum be always positive because k is
always positive.
For calculating dp[i][j] we need the values of all states that can make a sum j if we apply an
operation on a[i] and add it to the sum.
Below is the C++ implementation of this approach
435
Chapter 50. Check if array sum can be made K by three operations on it
Output:
Yes
Source
https://www.geeksforgeeks.org/check-if-array-sum-can-be-made-k-by-three-operations-on-it/
436
Chapter 51
Check if it is possible to
transform one string to another
Examples:
Approach:
Let DPi, j be 1 if it is possible to convert 1st i characters of s1 to j characters of s2, else
DPi, j =0. Close observations gives us two conditions to deal with.
437
Chapter 51. Check if it is possible to transform one string to another
Initially DP0, 0 =1, if DPi, j =1 then it is possible to check for next sets using following
conditions.
1. If s1[i] in upper case is equal to s2[j] then it is possible to convert i+1 characters of s1 to
j+1 characters of s2, hence DPi+1, j+1 =1.
2. If s1[i] is in lower case, then it is possible to delete that element and hence i+1 characters
can be converted to j characters of s2. Hence DPi+1, j =1.
If DPn, m =1, then it is possible to convert s1 to s2 by following conditions.
Below is the CPP illustration of the above approach.
C++
438
Chapter 51. Check if it is possible to transform one string to another
Java
439
Chapter 51. Check if it is possible to transform one string to another
440
Chapter 51. Check if it is possible to transform one string to another
}
}
// This code is contributed by Nikita Tiwari.
Output:
YES
Source
https://www.geeksforgeeks.org/check-possible-transform-one-string-another/
441
Chapter 52
Input : N = 3, M = 3, K = 7
mat[][] = { { 2, 3, 1 },
{ 6, 1, 9 },
{ 8, 2, 3 } };
Output : 6
Path (1, 1) -> (2, 2) -> (3, 3) to complete
journey to absorb 6 value.
Input : N = 3, M = 4, K = 9
mat[][] = {
{ 2, 3, 4, 1 },
{ 6, 5, 5, 3 },
{ 5, 2, 3, 4 }
};
Output : -1
442
Chapter 52. Check if possible to cross the matrix with given power
• Declare a boolean 3D matrix, say dp[ ][ ][ ], with N*M*(K+1) dimension such that
dp[ i ][ j ][ k ] is true if it possible to reach the square in the ith row and jth column
with exactly k value collected so far.
• We can write the recurrence dp[ i ][ j ][ k ] = true if either
dp[i-1][j][k-mat[i][j]] or
dp[i][j-1][k-mat[i][j]] or
dp[i-1][j-1][k-mat[i][j]]
443
Chapter 52. Check if possible to cross the matrix with given power
if (k == grid[i][j])
dp[i][j][k] = true;
}
// For first cell of each row
else if (i == 0) {
dp[i][j][k] = (dp[i][j][k] ||
dp[i][j - 1][k - grid[i][j]]);
}
// For first cell of each column
else if (j == 0) {
dp[i][j][k] = (dp[i][j][k] ||
dp[i - 1][j][k - grid[i][j]]);
}
// For rest of the cell
else {
// Down movement.
dp[i][j][k] = (dp[i][j][k] ||
dp[i][j - 1][k - grid[i][j]]);
// Right movement.
dp[i][j][k] = (dp[i][j][k] ||
dp[i - 1][j][k - grid[i][j]]);
// Diagonal movement.
dp[i][j][k] = (dp[i][j][k] ||
dp[i - 1][j - 1][k - grid[i][j]]);
}
}
}
}
// Finding maximum k.
int ans = 0;
for (ans = k; ans >= 0; ans--)
if (dp[n - 1][m - 1][ans])
break;
return ans;
}
// Driver Code
int main()
{
int n = 3, m = 4, p = 9;
444
Chapter 52. Check if possible to cross the matrix with given power
int grid[R][C] = {
{ 2, 3, 4, 1 },
{ 6, 5, 5, 3 },
{ 5, 2, 3, 4 }
};
cout << maximumValue(n, m, p, grid) << endl;
return 0;
}
Java
445
Chapter 52. Check if possible to cross the matrix with given power
446
Chapter 52. Check if possible to cross the matrix with given power
{ 5, 2, 3, 4 }};
System.out.println(maximumValue(n, m, p, grid));
}
}
// This code is contributed by Anant Agarwal.
C#
// C# program to find if it
// is possible to cross the matrix
// with given power
using System;
class GFG {
static int N = 105;
// static int R = 3;
// static int C = 4;
static int maximumValue(int n, int m, int p,
int[, ] grid)
{
bool[,, ] dp = new bool[N, N, N];
int i, j, k;
// Initializing array dp with false value.
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++)
dp[i, j, k] = false;
}
}
// For each value of dp[i][j][k]
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
for (k = grid[i, j]; k <= p; k++) {
// For first cell and for
// each value of k
if (i == 0 && j == 0) {
if (k == grid[i, j])
dp[i, j, k] = true;
}
// For first cell of each row
447
Chapter 52. Check if possible to cross the matrix with given power
else if (i == 0) {
dp[i, j, k] = (dp[i, j, k] ||
dp[i, j - 1, k - grid[i, j]]);
}
// For first cell of each column
else if (j == 0) {
dp[i, j, k] = (dp[i, j, k] ||
dp[i - 1, j, k - grid[i, j]]);
}
// For rest of the cell
else {
// Down movement.
dp[i, j, k] = (dp[i, j, k] ||
dp[i, j - 1, k - grid[i, j]]);
// Right movement.
dp[i, j, k] = (dp[i, j, k] ||
dp[i - 1, j, k - grid[i, j]]);
// Diagonal movement.
dp[i, j, k] = (dp[i, j, k] ||
dp[i - 1, j - 1, k - grid[i, j]]);
}
}
}
}
k = p;
// Finding maximum k.
int ans = 0;
for (ans = k; ans >= 0; ans--)
if (dp[n - 1, m - 1, ans])
break;
return ans;
}
// Driver code
public static void Main()
{
int n = 3, m = 4, p = 9;
int[, ] grid = { { 2, 3, 4, 1 },
{ 6, 5, 5, 3 },
{ 5, 2, 3, 4 } };
448
Chapter 52. Check if possible to cross the matrix with given power
Console.WriteLine(maximumValue(n, m, p, grid));
}
}
// This code is contributed by vt_m.
Output:
-1
Source
https://www.geeksforgeeks.org/check-possible-cross-matrix-given-power/
449
Chapter 53
Check whether row or column swaps produce maximum size binary sub-matrix with all 1s -
GeeksforGeeks
Given a binary matrix, the task is to find whether row swaps or column swaps give maximum
size sub-matrix with all 1’s. In a row swap, we are allowed to swap any two rows. In a
column swap we are allowed to swap any two columns. Output “Row Swap” or “Column
Swap” and the maximum size.
Examples:
Input : 1 1 1
1 0 1
Output : Column Swap
4
By swapping column 1 and column 2(0-based indexing),
index (0, 0) to (1, 1) makes the largest binary
sub-matrix.
Input : 0 0 0
1 1 0
1 1 0
0 0 0
1 1 0
Output : Row Swap
6
Input : 1 1 0
450
Chapter 53. Check whether row or column swaps produce maximum size binary sub-matrix
with all 1s
0 0 0
0 0 0
1 1 0
1 1 0
0 0 0
1 1 0
Output : Row Swap
8
The idea is to find both row swap and column swap maximum size binary submatrix and
compare.
To find the maximum sized binary sub-matrix with row swaps allowed, make a 2-D array,
say dp[i][j]. Each value of dp[i][j] contains the number of consecutive 1s on right side of (i,j)
in i-th row. Now, store each column in the 1-D temporary array one by one, say b[] and
sort, and find maximum b[i] * (n – i), since b[i] is indicating the sub-matrix width and (n –
i) is sub-matrix height.
Similarly, to find the maximum size binary sub-matrix with column swap allowed, find
dp[i][j], where each value contains the number of consecutive 1 below the (i, j) in j-th
column. Similarly, store each row in the 1-D temporary array one by one, say b[] and sort.
Find maximum b[i] * (m – i), since b[i] is indicating the submatrix height and (n – i) is
submatrix width.
Below is C++ implementation of this approach:
451
Chapter 53. Check whether row or column swaps produce maximum size binary sub-matrix
with all 1s
else
ryt[i][j] = ryt[i][j + 1] + 1;
}
}
// Travesing the 2d matrix from bottom-left.
for (int i = R - 1; i >= 0; i--)
{
for (int j = 0; j < C; ++j)
{
// If (i,j) contain 0, do nothing
if (mat[i][j] == 0)
dwn[i][j] = 0;
// Counting consecutive 1 down to (i,j).
else
dwn[i][j] = dwn[i + 1][j] + 1;
}
}
}
// Return maximum size submatrix with row swap allowed.
int solveRowSwap(int ryt[R + 2][C + 2])
{
int b[R] = { 0 }, ans = 0;
for (int j=0; j<C; j++)
{
// Copying the column
for (int i=0; i<R; i++)
b[i] = ryt[i][j];
// Sort the copied array
sort(b, b + R);
// Find maximum submatrix size.
for (int i = 0; i < R; ++i)
ans = max(ans, b[i] * (R - i));
}
return ans;
}
// Return maximum size submatrix with column
// swap allowed.
int solveColumnSwap(int dwn[R + 2][C + 2])
{
452
Chapter 53. Check whether row or column swaps produce maximum size binary sub-matrix
with all 1s
453
Chapter 53. Check whether row or column swaps produce maximum size binary sub-matrix
with all 1s
Output:
Row Swap
6
Source
https://www.geeksforgeeks.org/check-whether-row-column-swap-produces-maximum-size-binary-sub-matrix-1s/
454
Chapter 54
Choice of Area
This problem can be solved using recursion, after each time unit we can go to any of the
area but we will choose that area which ultimately leads to maximum survival time. As
455
Chapter 54. Choice of Area
recursion can lead to solving same subproblem many time, we will memoize the result on
basis of power A and B, if we reach to same pair of power A and B, we won’t solve it again
instead we will take the previously calculated result.
Given below is the simple implementation of above approach.
CPP
456
Chapter 54. Choice of Area
X, Y, Z, 3, memo));
break;
case 2:
temp = 1 + max(maxSurvival(A + X.a, B + X.b,
X, Y, Z, 1, memo),
maxSurvival(A + Z.a, B + Z.b,
X, Y, Z, 3, memo));
break;
case 3:
temp = 1 + max(maxSurvival(A + X.a, B + X.b,
X, Y, Z, 1, memo),
maxSurvival(A + Y.a, B + Y.b,
X, Y, Z, 2, memo));
break;
}
// store the result into map
memo[cur] = temp;
return temp;
}
// method returns maximum survival time
int getMaxSurvivalTime(int A, int B, area X, area Y, area Z)
{
if (A <= 0 || B <= 0)
return 0;
map< pair<int, int>, int > memo;
// At first, we can step into any of the area
return
max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo),
maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo),
maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo));
}
// Driver code to test above method
int main()
{
area X(3, 2);
area Y(-5, -10);
area Z(-20, 5);
int A = 20;
int B = 8;
cout << getMaxSurvivalTime(A, B, X, Y, Z);
return 0;
457
Chapter 54. Choice of Area
Python3
458
Chapter 54. Choice of Area
Output:
Source
https://www.geeksforgeeks.org/game-theory-choice-area/
459
Chapter 55
Choose maximum weight with given weight and value ratio - GeeksforGeeks
Given weights and values of n items and a value k. We need to choose a subset of these
items in such a way that ratio of the sum of weight and sum of values of chosen items is K
and sum of weight is maximum among all possible subset choices.
We can solve this problem using dynamic programming. We can make a 2 state dp where
dp(i, j) will store maximum possible sum of weights under given conditions when total items
are N and required ratio is K.
Now in two states of dp, we will store the last item chosen and the difference between sum
of weight and sum of values. We will multiply item values by K so that second state of dp
will actually store (sum of weight – K*(sum of values)) for chosen items. Now we can see
that our answer will be stored in dp(N-1, 0) because as last item is (N-1)th so all items
are being considered and difference between sum of weight and K*(sum of values) is 0 that
means sum of weight and sum of values has a ratio K.
After defining above dp state we can write transition among states simply as shown below,
460
Chapter 55. Choose maximum weight with given weight and value ratio
In below code a top-down approach is used for solving this dynamic programming and for
storing dp states a map is used because the difference can be negative also and the 2D array
can create problem in that case and special care need to be taken.
C++
461
Chapter 55. Choose maximum weight with given weight and value ratio
Java
462
Chapter 55. Choose maximum weight with given weight and value ratio
return Integer.MIN_VALUE;
}
// first make pair with last chosen item and
// difference between weight and values
Point tmp = new Point(last, diff);
if (hm.containsKey(tmp))
return hm.get(tmp);
/* choose maximum value from following two
1) not selecting the current item and calling
recursively
2) selection current item, including the weight
and updating the difference before calling
recursively */
hm.put(tmp,Math.max(maxWeightRec(wt, val, K, hm, last - 1, diff),
wt[last] + maxWeightRec(wt, val, K, hm,
last - 1, diff + wt[last] - val[last] * K)));
return hm.get(tmp);
}
// method returns maximum sum of weight with K
// as ration of sum of weight and their values
static int maxWeight(int wt[], int val[], int K, int N)
{
HashMap<Point, Integer> hm = new HashMap<>();
return maxWeightRec(wt, val, K, hm, N - 1, 0);
}
// Driver method
public static void main(String args[])
{
int wt[] = {4, 8, 9};
int val[] = {2, 4, 6};
int K = 2;
System.out.println(maxWeight(wt, val, K, wt.length));
}
}
// This code is contributed by Gaurav Miglani
Output:
12
463
Chapter 55. Choose maximum weight with given weight and value ratio
Source
https://www.geeksforgeeks.org/choose-maximum-weight-given-weight-value-ratio/
464
Chapter 56
Clustering/Partitioning an
array such that sum of square
differences is minimum
ways to make clusters (partitions). We define a function Cost(i) for the cluster, as
the square of the difference between its first and last element. If the current cluster is
Examples :
465
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
To solve the problem, we assume that we have k slabs. We have to insert them in some k
different positions in the array, which will give us the required partition scheme, and the
one having minimum value for f(x) will be the answer.
Naive solution:
If we solve the above problem by the naive method, we would simply take all the possibilities
and compute the minimum.
C++
466
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
return;
// If we have mad k partitions and have
// reached last element
if (par==k && i==n-1)
{
ans = min(ans, current_ans);
return;
}
// 1) Partition array at different points
// 2) For every point, increase count of
// partitions, "par" by 1.
// 3) Before recursive call, add cost of
// the partition to current_ans
for (int j=i+1; j<n; j++)
solve(j, par+1, a, n, k, current_ans +
(a[j]-a[i+1])*(a[j]-a[i+1]));
}
// Driver code
int main()
{
int k = 2;
int a[] = {1, 5, 8, 10};
int n = sizeof(a)/sizeof(a[0]);
solve(-1, 0, a, n, k, 0);
cout << ans << endl;
return 0;
}
Java
467
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
C#
468
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
469
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
Output:
20
Time Complexity: Its clear that the above algorithm has Time Complexity of .
Dynamic Programming:
We create a table dp[n+1][k+1] table and initialize all values as infinite.
Let us compute the value of dp[i][j]. we take an index m, such that m < i, and put a partition
next to that position such that there is no slab in between the indices i and m. It can be
seen simply that answer to the current scenario is dp[m][j-1] + (a[i-1]-a[m])*(a[i-1]-a[m]),
where the first term signifies the minimum f(x) till the element with j-1 partitions
and the second one signifies the cost of current cluster. So we will take the minimum of all
the possible indices m and dp[i][j] will be assigned the minimum amongst them.
C++
470
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
// Current ending position (After i-th
// iteration result for a[0..i-1] is computed.
for (int i=1;i<=n;i++)
// j is number of partitions
for (int j=1;j<=k;j++)
// Picking previous partition for
// current i.
for (int m=i-1;m>=0;m--)
dp[i][j] = min(dp[i][j], dp[m][j-1] +
(a[i-1]-a[m])*(a[i-1]-a[m]));
return dp[n][k];
}
// Driver code
int main()
{
int k = 2;
int a[] = {1, 5, 8, 10};
int n = sizeof(a)/sizeof(a[0]);
cout << minCost(a, n, k) << endl;
return 0;
}
Java
471
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
C#
472
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
473
Chapter 56. Clustering/Partitioning an array such that sum of square differences is
minimum
// This code is contributed by nitin mittal
Output:
20
Time Complexity: Having the three simple loops, the complexity of the above algorithm
is .
Improved By : nitin mittal
Source
https://www.geeksforgeeks.org/clusteringpartitioning-an-array-such-that-sum-of-square-differences-is-minimum/
474
Chapter 57
Coin game winner where every player has three choices - GeeksforGeeks
A and B are playing a game. At the beginning there are n coins. Given two more numbers
x and y. In each move a player can pick x or y or l coins. A always starts the game. The
player who picks the last coin wins the game. For a given value of n, find whether A will
win the game or not if both are playing optimally.
Examples:
Input : n = 5, x = 3, y = 4
Output : A
There are 5 coins, every player can pick 1 or
3 or 4 coins on his/her turn.
A can win by picking 3 coins in first chance.
Now 2 coins will be left so B will pick one
coin and now A can win by picking the last coin.
Input : 2 3 4
Output : B
C++
475
Chapter 57. Coin game winner where every player has three choices