[题目描述] 有 n 个瓶子排成一列，用 arr 表示。你每次可以选择能够形成回文连续子串的瓶子拿走，剩下的瓶子拼接在一起。返回你能拿走所有的瓶子的最小次数。 n<=500 arr[i]<=1000

在线评测地址：https://www.lintcode.com/problem/take-away-the-bottle/?utm_source=sc-v2ex-fks

样例 例 1:

输入：[1,3,4,1,5]  输出：3  说明：第一次先拿走[4]，剩余[1,3,1,5] 第二次拿走[1,3,1]，剩余[5] 第三次拿走[5] 

例 2:

输入：[1,2,3,5,3,1] 输出：2 

[题解] 利用区间 dp 解决。dpi 代表从第 i 位到第 j 位最少被消除的次数。然后我们在此基础之上向外延申。 对于 i 到 j 的区间，他的答案可能由 i 到 k 和 k+1 到 j 这两个区间的和，也就是 dpi = min(dpi, dpi + dpk + 1) 这只是其中一种可能性。

接着我们考虑另一种。当 arri=arrj 时，dpi = dpi + 1 意义是，若当前区间的前一个和后一个数刚好相等，那么这两个数可以直接跟随着当前区间的最后一次删除一起删除（我们无需考虑区间内部到底是做什么删除的，只要知道在最后一次删除前，这个区间剩余的和前后一定能组成新的回文子串）

public class Solution {     /**      * @param arr: the array of bottles      * @return: the minimum number of times you can take all the bottles      */     int[][] dp = new int[550][550];     public int takeAwayTheBottle(int[] arr) {         // Write your code here.         int i, j, k, l;         int n = arr.length;         for (i = 0; i < n; i++) {             for (j = 0; j < n; j++) dp[i][j] = n;         }          for (i = 0; i < n; i++) {             dp[i][i] = 1;         }         for (i = 0; i + 1 < n; i++) {             if (arr[i] == arr[i + 1]) dp[i][i + 1] = 1;             else dp[i][i + 1] = 2;         }         for (l = 2; l < n; l++) {             for (i = 0; i + l < n; i++) {                 j = i + l;                 if (arr[i] == arr[j]) {                     dp[i][j] = dp[i + 1][j - 1];                 }                 for (k = i; k < j; k++) {                     dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);                 }             }         }         return dp[0][n - 1];     } } 

更多语言代码参见：https://www.jiuzhang.com/solution/take-away-the-bottle/?utm_source=sc-v2ex-fks

大佬有話說 (0)