Hi,

I found some similar dynamic programming problems: 714, 907, 662.

Is there a formal name for this kind of problems?

## What is the name of this kind of DP problems?

**Moderator:** Board moderators

### Re: What is the name of this kind of DP problems?

Matrix Chain Multiplication :: more commonly known as MCM.

### Re: What is the name of this kind of DP problems?

I think MCM is 348 or 442 instead.

In 714, 907, and 662, we make k partitions of a given sequence and minimize the maximal partition.

We can use DP, optimized DP, or binary search to solve this kind of problems.

That is special. Thus I wonder if a formal and unique name exists.

In 714, 907, and 662, we make k partitions of a given sequence and minimize the maximal partition.

We can use DP, optimized DP, or binary search to solve this kind of problems.

That is special. Thus I wonder if a formal and unique name exists.

### Re: What is the name of this kind of DP problems?

Finally I found 662 is called 'p-median problem' after googling around 3 hours. It belongs to the 'location-allocation problem.'

The p-median problem is a well-known NP problem (but not for me ). There are many approaches to solve it, for example, integer programming. There are also many variants of this problem like the p-center problem, the uncapacitated facility location problem, and the range assignment problem.

Here is a reference: http://ramanujan.math.trinity.edu/tumat ... port96.pdf

The p-median problem is a well-known NP problem (but not for me ). There are many approaches to solve it, for example, integer programming. There are also many variants of this problem like the p-center problem, the uncapacitated facility location problem, and the range assignment problem.

Here is a reference: http://ramanujan.math.trinity.edu/tumat ... port96.pdf