Find minimum cost from top left corner to bottom right corner

May 13, 2018

Introduction

It is the algorithm to find the minimum cost from a matrix top left corner to bottom right corner.

Transcript

Here is my work in the mock interview. The interviewer told me that I should write the code after the mock interview, give him to review the code for next mock interview.

My next mock interview will be in Tuesday.

Mock interview 

Learning algorithm is such great experience. It is so much fun to work with a young graduate student around twenty five years old. He was very kind and also very encouraging. I spent first 5 to 10 minutes to think and communicate with the interviewer depth first search, compared to breadth first search. And then he kept asking me how you can improve the algorithm compared to depth first search. He did more than two times.

I finally came out the idea to use dynamic programming algorithm. Even though I have practice Deletion distance algorithm over 20 minutes last 12 months. But I still miss some dots to come to dynamic programming algorithm.

Arguments

I like to write down a few words about my analysis using depth first search is not optimal.

First, the algorithm is to find the minimum cost. There is no need to find actual path. Using depth first search of course takes extra effort to find path from source to destination.

The question is to ask minimum cost. I should quickly related to deletion distance.

I will do some research and figure out how I can come out dynamic programming algorithm without hints by the interviewer.

I have weakness to come out dynamic programming solution at the first place today.

Assignment

The interviewer told me to show him the code I write and he will give me some review next mock interview.

Follow up 

May 14, 2018
It is the algorithm called Leetcode 64: Minimum Path Sum.

I was asked if I worked on the problem before. I said that I did not. But actually I thought about the hackerrank contest I worked on similar algorithm. So I search all contests I played from oldest to latest one, I found the algorithm and blog called Manhantan 2.

I am so glad to learn that my last practice in the contest. I was so glad to see my hard work, and here is my C# algorithm written based on dynamic programming. The solution still has bugs with score 33.