132. 分割回文串 II

题意：

解题思路：

思路：
动态规划可以理解为：用一个数来表示一个集合，属性里求的最小值，dp[i]表示：将字符串从最左边到第i位分割成回文串，最小的分割次数；
1. k看成一个分界点，左边dp[k-1]的意思是从1~k-1分割成回文串的最小次数， 
2. 右边a[k~i]如果是一个回文串，则dp[i] = 左边回文串的最小分割次数 + 1，也就是dp[k - 1] + 1。

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function minCut($s) {
        $n = strlen($s);
        $s = ' '. $s;
        $g = array_fill(0, $n + 1, array_fill(0, $n + 1, 0));
        $f = array_fill(0, $n + 1, PHP_INT_MAX);
        for ($j = 1; $j <= $n; $j++) {
            for ($i = 1; $i <= $n; $i++) {
                if ($i == $j) $g[$i][$j] = true;
                else if ($s[$i] == $s[$j]) {
                    if ($i + 1 > $j - 1 || $g[$i + 1][$j - 1]) $g[$i][$j] = true;
                }
            }
        }
        $f[0] = 0;
        for ($i = 1; $i <= $n; $i++) {
            for ($j = 1; $j <= $i; $j++) {
                if ($g[$j][$i]) {
                    $f[$i] = min($f[$i], $f[$j - 1] + 1);
                }
            }
        }
        return $f[$n] - 1;
    }
    function minCut1($s) {
        $len = strlen($s);
        for ($i = 0; $i < $len; $i++) $dp[$i] = $i;
        for ($i = 0; $i < $len; $i++) {
            $this->update($dp, $s, $i, $i, $len);
            $this->update($dp, $s, $i, $i + 1, $len);
        } 
        return $dp[$len - 1];
    }
    function update(&$dp, $s, $left, $right, $len) {
        while ($left >= 0 && $right < $len && $s[$left] == $s[$right]) {
            if ($left == 0) $dp[$right] = 0;
            else $dp[$right] = min($dp[$right], $dp[$left - 1] + 1);
            $left--;
            $right++;
        }
    }
}