algorithm - 非特定方向计算中的动态规划方法

Question

我正在尝试解决 Ball Removal problem on topcoder , 将问题陈述粘贴到此处，因为访问此链接需要登录。

---

Problem Statement

You have N balls, where N is odd. The balls are numbered from 0 to N-1. In that order, they are arranged into a row going from the left to the right.

In addition to the number, each ball has either the word "left" or the word "right" written on it. For simplicity, we will use the character '<' instead of "left", and the character '>' instead of "right". You are given the labels on all balls as the String label. For each i, character i of label represents the word on ball i.

You will now repeat the following procedure:

• Choose a ball that is not at either end of the row of balls.
• If the chosen ball has the label '<', remove the chosen ball and also the ball immediately to the left of it. Otherwise, remove the chosen ball and also the ball to the right of it.
• Without reordering the remaining balls, push them together to get rid of the gap created in the previous step.

The process ends when only one ball remains in the row. That ball is called the survivor. Note that the numbers on the balls do not change during the process.

Find all possible survivors. Your method must return a String containing exactly N characters. If ball i can be the survivor, character i of the return value must be 'o' (lowercase oh). Otherwise, the corresponding character must be '.' (a period).

Constraints

• label will contain between 3 and 49 characters, inclusive.
• label will contain an odd number of characters.
• Each character of label will be either '>' or '<'.

Examples
"<<>" Returns: "..o"

Initially, you have three balls. Since you cannot choose balls at the ends of the row, you have to choose ball 1. As its label is '<', you remove balls 0 and 1. Hence the only possible survivor is ball 2. 1) ">>><<" Returns: "o...o"

If you choose ball 2 or ball 3 first, you have to choose ball 1 next, and the survivor will be ball 0. If you choose ball 1 first, you have to choose ball 3 next, and the survivor will be ball 4.

2) "<<><<" Returns: "....o"

3) "<><<><>" Returns: "o.....o"

4) ">>><<<>>>>><<<>" Returns: "o.....o.o.....o"

---

我正在考虑使用动态编程方法来解决这个问题，我正在考虑使用一个 bool 数组来标记哪些字符已被删除，然后找出哪个是左下一个右下一个，但这使得该方法效率很低并且我必须写一个递归方法。为了实现动态编程方法，我需要维护一个状态。但是我无法弄清楚我应该保留什么作为状态，在我看来状态是当前字符串和当前索引的组合，但是为状态维护字符串对我来说似乎不正确。

我面临的另一个问题是，在这种情况下，如果我改变方向，结果也会改变，如果我从左向右移动，我可能也需要从右向左移动，所以我没有特定的方向。 请帮助我找到解决此问题的正确方法。

Answer 1

状态可以是 bool 值 - DP[left][right][isLeftBoundary][isRightBoundary]。

这意味着如果从left开始到right结束的子串可以完全消除。

isLeftBoundary 只是一个 bool 标志，如果 left 符号是字符串的最左边。

isRightBoundary 只是一个 bool 标志，如果 right 符号是字符串的最右边。

如果 DP[0][i - 1][1][0] 和 DP[i + 1][N][0][1] 是true，表示位置i的球可以保留。

    int canDelete(int l, int r, int st, int en)
    {
        if (l > r) return 1; //we succeeded in removing the whole string

        if (DP[l][r][st][en] != -1)
           return DP[l][r][st][en];

        int ans = 0;

        //i is the last removed ball, which will eliminate the whole string[l, r]
        for (int i = l + st; i <= r - en; i++) 
        {
            if (inp[i] == '<') //it will remove a ball to the left, but which one?
            {
                for (int j = l; j < i; j++) //ball i will remove ball j
                {       
                     if (canDelete(l, j - 1, st, 0) 
                      && canDelete(j + 1, i - 1, 0, 0) 
                      && canDelete(i + 1, r, 0, en))
                         ans = 1;       
                }
            }
            else
            if (inp[i] == '>') //it will remove a ball to the right, but which one?
            {
                for (int j = i + 1; j <= r; j++) //ball i will remove ball j
                {       
                     if (canDelete(l, i - 1, st, 0) 
                      && canDelete(i + 1, j - 1, 0, 0) 
                      && canDelete(j + 1, r, 0, en))
                         ans = 1;       
                }       
            }
        }

        return ans;
    }