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( n² x m²) space. The efficient way is O(n x m), using dynamic programming.

Share the practice C# code, here is the link.