leetcode-go/oj/tencent-2019-summer/no3/card.go

package main

import "fmt"

const MOD int = 1000000007

func main() {
	var n, s int
	fmt.Scan(&n, &s)
	cards := make([]int, n)
	for i := range cards {
		fmt.Scan(&cards[i])
	}
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, s+1)
	}
	dp[0][0] = 2
	if s != 0 {
		dp[0][1] = 1
	}
	for i := 1; i < n; i++ {
		for j := 0; j <= s; j++ {
			dp[i][j] = (2 * dp[i-1][j]) % MOD // Not win
			if j > 0 {
				dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD // Win
			}
		}
	}
	fmt.Println(dp[n-1][s])
}