leetcode-go/leetcode/hard/664.strange-printer.go

func strangePrinter(s string) int {
	n := len(s)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	// dp[i][j] means the min move to build string s[i:j+1].
	// So, dp[i][j] = 0, j < i (empty string)
	//              = dp[i][j-1] + 1 (init)
	//              = min(dp[i][j], dp[i][k]+dp[k+1][j-1]), s[k] == s[j]
	return dfs(s, 0, n-1, dp)
}

func dfs(s string, i, j int, dp [][]int) (res int) {
	if j < i {
		return
	} else if 0 < dp[i][j] {
		return dp[i][j]
	}
	res = dfs(s, i, j-1, dp) + 1
	for k := i; k < j; k++ {
		if s[k] == s[j] {
			res = minInt(res, dfs(s, i, k, dp)+dfs(s, k+1, j-1, dp))
		}
	}
	dp[i][j] = res
	return
}

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