688. Knight Probability in Chessboard

March 10, 2018

Introduction

Dynamic programming algorithm is more advanced compared to recursive function, depth first search algorithm. I like to write down some note to document my practice, time spent is longer than three hours.

Algorithm practice

I did read one blog to document the analysis of the algorithm with the code, so I went over analysis word by word, and organized the idea first and put into the gist. But I could not understand the algorithm.

So I continued to search more blogs to read, and then I found one with the graph to explain three dimension dynamic programming. I understood the idea to apply dynamic programming algorithm.

Next I worked on code from discussion panel and then converted to the C# code. But it still took me more than one hour, I had to debug the code and pass the failed test case.

It is so interesting to learn the algorithm by going over the steps. It is not difficult but it took me a few hours. I think that it should take less than one hour in total.

Here is the gist I created for understanding the dynamic programming algorithm after I read a few coding blog and one discussion on Leetcode.com.

Here is the code to implement in two dimension array instead of 3 dimension, since we do not need to save all intermediate steps.

Here is the C# code to pass all test cases on Leetcode online judge 688.