At this point in the series, sufficient concepts and information about Dynamic Programming have been covered, such as optimal substructure, overlapping sub-problems, problem analysis and the techniques at arriving at the recurrence relation. From this point on, this series will pivot to applying those concepts and techniques to solve simple to more challenging Dynamic Programming problems.
In this blog, we will tackle the “Target Sum” Dynamic Programming problems using the top down approach.
Given a target sum and an unsorted array of positive integers, we need to answer the following questions, and they are in the increasing order of complexity.
From the previous blog (Top Down & Bottom Up), we learned the essence of solving Dynamic Programming problems is to derive the recurrence relation, and then use either the top-down or bottom-up approach to translate it to code. Therefore it is important to master the problem analysis and the techniques to derive a recurrence relation. This blog and the future ones will focus on sharing the insights to help with this.
This blog will use a simple (level 1) Dynamic Programming problem called Climbing Stairs to illustrate the problem analysis and the techniques at arriving at a recurrence relation.
The previous blog post “Dissecting Dynamic Programming — The Beginning” described two important concepts in Dynamic Programming, then illustrated them using the Fibonacci Sequence example, and finally it ended with some details about translating a recurrence relation to code.
This blog post will share a few insights about how to translate a recurrence relation of a Dynamic Programming problem to commonly used solution approaches — “top down” and “bottom up”. First let’s make sure we are on the same page regarding what a “recurrence relation” is.
If the term “recurrence relation” is somewhat of vague to you, here is one…
I find Dynamic Programming fascinating and intellectually challenging. The goal of this “Dissecting Dynamic Programming” series is to share the insights I gather while studying and solving this class of problem.
“The Best Way to Learn Something is to Teach it to Someone Else” is one of the well-known proverbial wisdom quotes. This blog series is intended for the following reasons:
To kick off this series, the below sections will describe…
An awesome post from HBR website provides many great management tips. Below is a summary of the tips that are resonated with me. Along the way, I inject a few suggestions of my own.
We all have a to-do list and it gets longer and longer. Here is one simple tip to keep your to-do list under control:
With the release of Apache Spark 2.4 in November 2018, the Data Source V2 APIs became more stable. The design and the work for this major improvement is documented in Jira ticket SPARK-15689. If you trace through the design document and the sub-tasks of the aforementioned Jira ticket, you will discover that the work was started before the release of Apache Spark 2.3 and some of the APIs enhancements were released in Apache Spark 2.3. To my surprise, there were breaking changes in the Data Source V2 APIs when Apache Spark 2.4 came out.