Demystifying Dynamic Programming with Java — Part I

Akshat Srivastava

Published in

Geek Culture

5 min readSep 17, 2021

If you can’t remember the past, you are condemned to repeat it. ~Dynamic Programming

Hold Tight, Let’s get started.

Before starting, read this quote to boost up your motivation.

If you can’t fly, then run, if you can’t run, then walk, if you can’t walk, then crawl, but by all means, keep moving. :– Martin Luther King Jr.

Now, let’s start :)

What is recursion?

It is the process of repeating itself similarly for smaller problems, or you can say, calling the same function in a code for a smaller subproblem till the base condition hits.

The above pictorial representation can help you to understand recursion.

So, you must be thinking what does recursion do in dynamic programming??

What is Dynamic Programming?

Dynamic programming is nothing but an optimization over plain recursion. Whenever we see a repeated recursive call for a smaller subproblem we can optimize that recursive call with the help of dynamic programming. The idea is simply to store the result so that we don’t have to re-compute that subproblem again and again.

Dynamic programming = recursion + memoization.

Let’s understand with the help of an example

Fibonacci Number: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55….

It is simply the summation of the previous number and the current number.

Return the n-th Fibonacci Number using the recursive method:

You can see we are calling the function for (n-1) and (n-2) till the base conditions are hit and adding to get another new number. It has exponential time complexity.

Return the n-th Fibonacci Number using DP method:

In the above gist, you can see that I have saved the previous value in the dp array. It has linear time complexity.

Types of Knapsack:

Fractional Knapsack:- Requires Greedy paradigm to solve the questions.
0/1 Knapsack:- Requires Dynamic Programming.
Unbounded Knapsack:- Requires Dynamic Programming with minor changes.

Bottom-Up Approach aka Tabulation Method

In this method, we initialize the first row and the first column of the 2d matrix, and the answers get accumulated in every cell and eventually, at the last cell of the 2d matrix you will get the required answer, the values getting stored at every cell is nothing but the values of the smaller subproblem which are getting stored.

We will be solving the question with the help of tabulation (bottom up) approach.

0/1 Knapsack

Q) You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity for each item.
In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that the sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0–1 property).

Input

val[] = {60, 100, 120}

wt[] = {10, 20, 30}

W = 50

Output

220

Breakdown:

You have N items.
The total Capacity of the knapsack is W.
val[0…N-1] array depicts the value array, wt[0…N-1] array depicts the weights of the item.
You have to maximize the profit also you can only have one quantity of each item.

Approach to solve the question:

Make a 2d array dp matrix — dp[N+1][W+1], +1 because we will start initializing from the 0th row and 0th column.

X-axis (rows) of the dp matrix will denote the capacity of the knapsack 0,1,2…..W, because we will be storing the answer of smaller subproblems.

Y-axis (columns) of the dp matrix will denote the length of the arrays 0,1,2…..N

We will initialize the 0th row and 0th column with 0 because if the val array or wt array is empty then the max profit will be 0 as we cannot any thing to the knapsack and if the W is 0 then we cannot add anything to the knapsack therefore the profit will be 0.

At last, your answer will be stored at dp[n][W].

Try out the problem here 0/1 Knapsack.

Unbounded Knapsack

Unbounded knapsack is also known as Knapsack with duplicate items. Here duplicity is allowed, unlike 0/1 knapsack.

We will tackle this problem with the Tabulation Method

Q) Given a set of N items, each with a weight and a value, and a weight limit W. Find the maximum value of a collection containing any of the N items any number of times so that the total weight is less than or equal to W.

Input

val[] = {1,4,5,7}

wt[] = {1,3,4,5}

W = 8

Output

Breakdown:

You have N items.
The total Capacity of the knapsack is W.
val[0…N-1] array depicts the value array, wt[0…N-1] array depicts the weights of the item.
You have to maximize the profit also you can select one item multiple times.

Approach

At last, your answer will be stored at dp[n][W].

The only minor change in Unbounded Knapsack is in line number 17 of the above code.

In 0/1 Knapsack we cannot select 1 item multiple time therefore we were reducing the size of the array because we don’t want to include it. Hence the code line was :

dp[i][j] = Math.max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])

In Unbounded Knapsack we can select 1 item multiple times therefore we are not reducing the size of an array.

dp[i][j] = Math.max(val[i-1]+dp[i][j-wt[i-1]],dp[i-1][j])

Try out the problem here Unbounded Knapsack

Closing Notes:

Thank you for reading this article so far, also all the best for your future endeavors. I hope this article helped you in understanding this concept, also I hope you all will also become the optimized version of yourself.

Stay tuned for more articles.

In the next part we will solve more interesting problems on String and much more :)