2021-08-17：谷歌面试题扩展版，面值为1~N的牌组成一组

package main

import "fmt"

func main() {
    ret := f2(5, 2, 3)
    fmt.Println(ret)
}
func f1() float64 {
    return p1(0)
}

// 游戏的规则，如上
// 当你来到cur这个累加和的时候，获胜概率是多少返回！
func p1(cur int) float64 {
    if cur >= 17 && cur < 21 {
        return 1.0
    }
    if cur >= 21 {
        return 0.0
    }
    w := 0.0
    for i := 1; i <= 10; i++ {
        w += p1(cur + i)
    }
    return w / 10
}

// 谷歌面试题扩展版
// 面值为1~N的牌组成一组，
// 每次你从组里等概率的抽出1~N中的一张
// 下次抽会换一个新的组，有无限组
// 当累加和<a时，你将一直抽牌
// 当累加和>=a且<b时，你将获胜
// 当累加和>=b时，你将失败
// 返回获胜的概率，给定的参数为N，a，b
func f2(N int, a int, b int) float64 {
    if N < 1 || a >= b || a < 0 || b < 0 {
        return 0.0
    }
    if b-a >= N {
        return 1.0
    }
    // 所有参数都合法，并且b-a < N
    return p2(0, N, a, b)
}

// 游戏规则，如上，int N, int a, int b，固定参数！
// cur，目前到达了cur的累加和
// 返回赢的概率
func p2(cur int, N int, a int, b int) float64 {
    if cur >= a && cur < b {
        return 1.0
    }
    if cur >= b {
        return 0.0
    }
    w := 0.0
    for i := 1; i <= N; i++ {
        w += p2(cur+i, N, a, b)
    }
    return float64(w) / float64(N)
}

// f2的改进版本，用到了观察位置优化枚举的技巧
// 可以课上讲一下
func f3(N int, a int, b int) float64 {
    if N < 1 || a >= b || a < 0 || b < 0 {
        return 0.0
    }
    if b-a >= N {
        return 1.0
    }
    return p3(0, N, a, b)
}

func p3(cur int, N int, a int, b int) float64 {
    if cur >= a && cur < b {
        return 1.0
    }
    if cur >= b {
        return 0.0
    }
    if cur == a-1 {
        return 1.0 * float64(b-a) / float64(N)
    }
    w := p3(cur+1, N, a, b) + p3(cur+1, N, a, b)*float64(N)
    if cur+1+N < b {
        w -= p3(cur+1+N, N, a, b)
    }
    return float64(w) / float64(N)
}

// f3的改进版本的动态规划
// 可以课上讲一下
func f4(N int, a int, b int) float64 {
    if N < 1 || a >= b || a < 0 || b < 0 {
        return 0.0
    }
    if b-a >= N {
        return 1.0
    }
    dp := make([]float64, b)
    for i := a; i < b; i++ {
        dp[i] = 1.0
    }
    if a-1 >= 0 {
        dp[a-1] = 1.0 * float64(b-a) / float64(N)
    }
    for cur := a - 2; cur >= 0; cur-- {
        w := dp[cur+1] + dp[cur+1]*float64(N)
        if cur+1+N < b {
            w -= dp[cur+1+N]
        }
        dp[cur] = float64(w) / float64(N)
    }
    return dp[0]
}