In some dynamic programming problems, I notice that my cache table is very sparse. In other words, if I define a table as DP[i][j], i<=10^6, j<=10^2, only a fraction of the table is used and the rest is -1.
So my question is, is it common practice to use a hashmap instead to store (i, j) pairs with their DP value and access them in average O(1) time rather than storing them in the sparse table to save memory?
First of all, Yes you can use hashmap instead of the array for dynamic programming problems. But there are some limitations as well as well as benefits for using a hashmap.
When you use a hashmap for this particular case(dynamic programming), it reduces memory complexity but simultaneously it will increase the constant factor of your code. That means if you can perform 10^{8} operations/second with the help of array, then you will be able to perform around 10^{7} operations/second when used hashmap due to its constant factor although with the same complexity of the algorithm.
So if possible to declare that much size of the array, use array otherwise use the hashmap.
