[Êý¾Ý½á¹¹ÓëËã·¨]LintCode1884ÄÃ×ßÆ¿×Ó-Çø¼äÐͶ¯Ì¬¹æ»®

lintcode 1884
n = arr.length
dp[i][j] ´ú±íÄÃ×ß$i¡«j$Æ¿×ÓËùÐèÒªµÄ×îÉÙ´ÎÊý.
³õʼ»¯Ìõ¼þ

1. $fori=0:n?1forj=i:n?1:$ dp[i][j] = n
2. $fori=0:n?1:$ dp[i][i] = 1
3. $fori=1:n?1:$ dp[i-1][i] = 1 $ifarr[i?1]=arr[i]$, dp[i-1][i] = 2 $ifarr[i?1]ªÁ=arr[i]$
   ״̬תÒÆ
4. $forl=2:n?1fori=0:n?1,j=i+l:$ dp[i][j] = dp[i+1][j-1] $ifarr[i]=arr[j]$
5. $fork=i:j?1:$ dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]))

Java

public class Solution {
    public int takeAwayTheBottle(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) dp[i][j] = 1;
                else if (i == j-1) {
                    if (arr[i] == arr[j]) dp[i][j] = 1;
                    else dp[i][j] = 2; 
                } else dp[i][j] = n;
            }
        }
        for (int l = 2; l < n; l++) {
            for (int i = 0; i < n && i+l < n; i++) {
                int j = i+l;
                if (arr[i] == arr[j]) dp[i][j] = dp[i+1][j-1];
                for (int 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];
    }
}

Go

func takeAwayTheBottle (arr []int) int {
    //base cace
    n := len(arr)
    dp := make([][]int,n)
    for i,_ := range dp {
        dp[i] = make([]int,n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i == j {
                dp[i][j] = 1
            } else {
                dp[i][j] = n
            }
        }
    }
    for i := 0; i+1 < n; i++ {
        if arr[i] == arr[i+1] {
            dp[i][i+1] = 1
        } else {
            dp[i][i+1] = 2
        }
    }
    //dp
    for l := 2; l < n; l++{
        for i := 0; i+l < n; i++ {
            r := i+l
            if arr[i] == arr[r] {
                dp[i][r] = dp[i+1][r-1] 
            }
            for k := i; k < r; k++ {
                dp[i][r] = min(dp[i][r],dp[i][k]+dp[k+1][r])
            }
        }
    }
    return dp[0][n-1]
}

func min(x,y int) int {
    if x < y {return x}
    return y
}