p://www.careercup.com/question?id=686684

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.

这个题目应该怎么分解DP呢?

我看有几个人都是建议

F(n) = max{F(n-2) + v({a(n-1), a(n)}), F(n-3) + v({a(n-2), a(n-1), a(n)})}

首先我不知道这种分解是不是正确

其次,如果是这样的话, 我不太明白, 为什么可以分解成F(n-2) + v({a(n-1), a(n)}),

但是不考虑 v({a(0),a(1)})+F({a[2]…a[n-1]})

### Like this:

Like Loading...

*Related*