Thursday, June 25, 2015

Cache design, dynamic programming - matrix region sum

June 25, 2015

Introduction

It is my firs time to read the algorithm and I am so surprised to learn the algorithm. I love the learning and also very happy to read the blog with good and very clear explanation of the algorithm.

Problem statement:
Given the integer matrix, top left and bottom right coordinates of the rectangular region, calculate the region sum.
Here is one of blogs I like to read and share. 

Make it more time efficient


Naive solution, O(n x m) calculation of addition to get the sum. How to get it as O(1) using cache, how big the cache space?
Naive way to design the cache, it takes O( n2 x m2) space. The efficient way is O(n x m), using dynamic programming.
Share the practice C# code, here is the link. 

No comments:

Post a Comment