Leetcode 1000. Minimum Cost to Merge Stones (II)

March 7, 2019

Introduction

It is a hard level algorithm. I also have chance to practice some combinatorics I learned from 1996 to 1997 FAU graduate course.

Series review

Good job to explain the recurrence formula. I write the formula by myself in the following:
How to build recurrence formula?

F(n-1) = F(n) - K + 1 <- we merge K piles to one pile. For example, F(n) is the array with length n, then F(n-1) array's length should be n - (K - 1).
F(n-2) = F(n) - K + 1
...
F(1) = F(2) - K + 1

Add above all formula's left item together, right item together. Both sides have common items to remove, F(2), F(3), ..., F(n-1). So left side and right side can be simplified in the following:
F(1) = F(n) - m * (K - 1).
In other words, 1 = n - m * (K - 1).
We can conclude that array's length n, (n - 1)/ (K - 1) = m, which means (n - 1)% (K - 1) == 0.