leetcode-go/written-exam/360-2018-spring/2-cut-balloon.go

package main

import "fmt"

const MOD int = 1000000007

func main() {
	var n int
	fmt.Scan(&n)
	color := make([]int, n)
	for i := range color {
		fmt.Scan(&color[i])
	}
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		dp[i] = dp[i-1]
		var set [10]bool
		set[color[i-1]] = true
		for j := 1; 0 < i-j; j++ {
			if !set[color[i-j-1]] {
				dp[i] = (dp[i] + dp[i-j-1]) % MOD
				set[color[i-j-1]] = true
			} else {
				break
			}
		}
	}
	fmt.Println(dp[n])
}