google : 记电话号码

//You are given a String number containing the digits of a
//phone number (the number of digits, n, can be any positive integer) . To help you memorize
//the number, you want to divide it into groups of contiguous digits. Each group must contain
//exactly 2 or 3 digits. There are three kinds of groups:
//• Excellent: A group that contains only the same digits. For example, 000 or 77.
//• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
//• Usual: A group in which all the digits are distinct. For example, 123 or 90.
//The quality of a group assignment is defined as
//2 × (number of excellent groups) + (number of good groups)
//Divide the number into groups such that the quality is maximized. Design an efficient
//algorithm to return the solution that maximizes the quality.

f(i) = max(
f(i - 2) + 2 ---> if number(i - 1) == number(i),
f(i - 3) + 2 ---> if number(i - 2) == number(i - 1) == number(i),
f(i - 3) + 1 ---> if number(i - 2, i - 1, i) is Good,
f(i - 1)
)

回复 2# Etrnls
嗯，好像是非常典型的DP问题，不过还需要加上f(i-1)吗？每个group不是必须是2或3个digits吗

回复 3# darksteel

囧……写错了@@
最后那个f(i - 1)应该是f(i - 2)...

唉……最近越来越2了……
最后那个f(i - 1)应该是两项，f(i - 2), f(i - 3)

回复 5# Etrnls
没有路线错误就好，真正写的时候肯定会注意到的

恩，简单的DP问题