Dynamic programming

As with many computer science algorithms and techniques, dynamic programming has a mathematical background. The concept of dynamic programming was conceived in the 1940s as a mathematical optimization technique.

There are two main ways of applying dynamic programming to a problem: one is called memoization and the other is the bottom up approach.

A prerequisite for dynamic programming is that the problem has an optimal substructure and overlapping subproblems.

Memoization usually involves coming up with a recursive algorithm for the problem and then, making  use of the already calculated results in the recursion so that the number of recursive calls are reduced significantly.

The bottom up approach involves coming up with the solution for the subproblem and then building the results in a bottom up way  by storing the results in a table. The result of this usually ends up in the last element of the table.

A common example for dynamic programming is the fibonacci series problem. The fibonacci series is defined as a number at index n being the sum of the numbers at the previous two indices in the series: n-1 and n-2. The base case is that the series always starts with 1, 1, 2,…

Using memoization, the solution to the fibonacci series problem is as follows:

memo = {}

def fibonacci(n):
    global memo

    if n in memo:
        return memo[n]

    if n <= 2:
        return 1

    f = fibonacci (n-1) + fibonacci (n-2)
    memo[n] = f
    return f

Using the bottom up approach, the solution to the fibonacci series problem is as follows:

def fibonacci(n):
    memo = {}

    for i in range(n):
        if i<=1:
            memo[i] = 1
            continue

        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]

Designing good classes and functions

The principle of having a class or a function do only one thing is a very important and useful heuristic. This is known as the single responsibility principle.

Also, it is important to correctly name the classes and functions. The convention followed is to have class names be nouns and function names be verbs.

Doing these two things ensures that anyone looking at any class and function can quickly understand what it does and can plug in or remove or modify these without any issues.

For example, the below python code, which follows the above principles, is pretty easy to understand and follow along:


class ColorRetriever(object):
    def __init__(self):
      self.color = get_color()

    def pick(self):
      return self.color

Tackling coding problems

It is often said that when tackling coding problems, programmers tend to try out all sorts of combinations of statements before getting it right. This is true. However, what gives a program its edge is going the extra distance and making the program nice and readable for the next person who comes along to maintain it or change it. This quote perhaps sums it up nicely:

Always code as if the person who ends up maintaining your code is a violent psychopath who knows where you live.

Making programs readable

Often, programs which are written in a readable way utilizing the principles of clean code make for good long-term code.

Technical debt is defined as the cost of rework of a software as a result of choosing an easy approach instead of choosing a better approach which may take longer to implement.

Lowering technical debt requires some responsible design and clean coding practices, among other things, from the get-go.

Why we code

The purpose behind coding is to produce results using complicated algorithms which would be difficult and fraught with error if done manually. So, we take the hit at the beginning of coming up with good programs, written in a readable manner for future maintenance.