Many days ago I showed how to use dynamic programming to solve the stones game question. see here
Dynamic programming is no doubt a very efficient way to solve this question. However, a recursive algorithm would be more intuitive and easy to understand, hence give better maintainability. With a little hack, e.g. caching, we can still reach a pretty good performance using recursion.
Problem reviewed
from lintcode
There is a stone game. At the beginning of the game, the player picks n piles of stones in a line.
The goal is to merge the stones in one pile observing the following rules:
At each step of the game, the player can merge two adjacent piles to a new pile.
The score is the number of stones in the new pile.
You are to determine the minimum of the total score.
Example
For [4, 1, 1, 4], in the best solution, the total score is 18:
- Merge second and third piles => [4, 2, 4], score +2
- Merge the first two piles => [6, 4]，score +6
- Merge the last two piles => [10], score +10
Other two examples:
[1, 1, 1, 1] return 8
[4, 4, 5, 9] return 43
/**
* GIVEN:
* A stone game:
* - a list of stone numbers in a line
* - you can merge two adjacent stone into a pile
* - and you can merge two adjacent piles/stones into one bigger pile
* - each time you merge one pile, you get a score
* - score = total score of left pile + total score of right pile
*
* ASK:
* Mimnimum of the total score
*
* ANALYSIS:
* Think from the last step:
* There are so many different ways to merge the stones
* But at the end you will have only two piles
* And you will just merge the two piles into one
* Getting the score = all stones add up together
*
* Thus:
* - the score you get in the last-time merge is known
*
* Now think a bit more:
* Each pile was originally merged from two smaller piles
* With a score = all stones of left pile and right pile added up together
*
* Deduce the formula:
*
* possibilities of final scores of a list of N stones =
* sum of all stones in the list
* +
* possibilities of the sum of the final scores of merging each of its two sublists,
* where one list has X stones and theother list has Y stones
*
* and you can go on and on...
*
* so we can see this is a recursive function
* that keeps processing a list of N stones
* and inside the function you need a loop
* to iterate the {(x, y) | x + y = N}
*
* and our target is to find the smallest in this greate searching space.
*
* With this in mind we know how to test the correctness now.
* However, this search is not optimal in terms of performance.
*
* We just want the minimal, let's optimize:
* the minimal score of merging a list of N stones =
* sum of all stones in the list
* +
* minimal score of possibilities of the sum of the final scores
* of merging each of its two sublists, where one list has X stones
* and the other list has Y stones
*
*/
public class Solution {
/**
* @param A: An integer array
* @return: An integer
*/
public int stoneGame(int[] A) {
if (A == null || A.length <= 0) return 0;
this.stones = A;
this.cache = new int[A.length][A.length];
int start = 0;
int end = A.length - 1;
return getScore(start, end);
}
private int[][] cache = null;
private int getScore(int start, int end) {
// cache logic
if (this.cache[start][end] != 0) return this.cache[start][end];
// real business logic
if (start >= end) return 0;
int rangeSum = sumRange(start, end);
boolean isAdjacent = (start + 1) == end;
int answer = 0;
if (isAdjacent) {
answer = rangeSum;
} else {
int minMergeScore = minScore(start, end);
answer = rangeSum + minMergeScore;
}
// cache and return answer
this.cache[start][end] = answer;
return answer;
}
private int minScore(int start, int end) {
int min = Integer.MAX_VALUE;
for(int x = start; x < end; x++) {
int score = getScore(start, x) + getScore(x + 1, end);
min = Math.min(min, score);
}
return min;
}
private int[] stones = null;
private int sumRange(int start, int end) {
int sum = 0;
for(int i = start; i <= end; i++) {
sum += this.stones[i];
}
return sum;
}
}
