Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of partitioning the set of agents into exhaustive and disjoint coalitions so as to maximize social welfare. This coalition structure generation problem is extremely challenging due to the exponential number of partitions that need to be examined. Specifically, given n agents, there are O(n\^ n) possible partitions. To date, the only algorithm that can find an optimal solution in O(3\^ n) is the Dynamimc Programming (DP) algorithm, due To Rothkopf et al. However, one of the main limitations of DP is that it requires a significant amount of memory. In this paper, we devise an Improved Dynamic Programming algorithm (IDP) that is proven to perform fewer operations than DP (e.g. 38.7% of the operations given 25 agents), and is shown to use only 33.3% of the memory in the best case, and 66.6% in the worst.