Leetcode - < dynamic planning special> Jianzhi offer 19, 49, 60

The finger of the sword Offer 19. Regular Expression Matching 、49. Ugly number 、60. n The number of dice

Title Description ：
[19]
Please implement a function to match the contains ’. ‘ and ’‘ Regular expression of . Characters in pattern ’.‘ Represents any character , and ’' Indicates that the character in front of it can appear any number of times （ contain 0 Time ）. In the subject , Matching means that all characters of a string match the whole pattern . for example , character string "aaa" With the model "a.a" and "abaca" matching , But with "aa.a" and "ab*a" No match .
[49]
We will include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. Seek the order from small to large n Ugly number .
[60]
hold n A dice on the ground , The sum of the points on the up side of all dice is s. Input n, Print out s The probability that all possible values of the .

You need to return the answer with an array of floating-point numbers , Among them the first i The elements represent this n The number of points that a die can roll i The probability of the smaller one .

Key points of investigation ：
The first 19 topic Two dimensional state array , among dp[i][j]=true Express s[0, i) And p[0, j) Pattern matching
The first 49 topic The three pointers point to 2,3,5 Corresponding position , Put the minimum number of products each time
The first 60 topic Make f(n,s) It's a two-dimensional matrix , Expressed as n The number of dice is s The situation of ; Yes f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)

The first 19 topic

func isMatch(s string, p string) bool {
    
	sLen, pLen := len(s), len(p)
	var dp [][]bool
	for x := 0; x <= sLen; x++ {
    		// Create an array of storage states 
		ar := make([]bool, pLen+1)		// among dp[i][j]=true Express s[0, i) And p[0, j) Pattern matching 
		dp = append(dp, ar)
	}
	dp[0][0] = true // The boundary conditions ,  If from 0 At the beginning, the boundary is -1, So we store the results in 1——(Len+1), So pay attention to dp Than s and p More than a 
	for i := 0; i <= sLen; i++ {
    
		for j := 1; j <= pLen; j++ {
    
			if p[j-1] == '*' {
    		//dp[i][j-2] Express '*' The number of Representatives is 0, The back says '*' The number of Representatives is 1
				dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j])
			} else {
    
				dp[i][j] = i > 0 && (s[i-1] == p[j-1] || p[j-1] == '.') && dp[i-1][j-1]
			}
		}
	}
	return dp[sLen][pLen]
}

The first 49 topic

func nthUglyNumber(n int) int {
    
    res := make([]int, n)
    res[0] = 1
    p2, p3, p5 := 0, 0, 0
    for i := 1;i < n;i ++{
    
        res[i] = min(res[p2] * 2, res[p3] * 3, res[p5] * 5)
        if res[i] == res[p2] * 2{
       // Not available if else, When multiple minimum values are equal , It should be moved back at the same time to ensure weight removal 
            p2 ++
        }
        if res[i] == res[p3] * 3{
    
            p3 ++
        }
        if res[i] == res[p5] * 5{
    
            p5 ++
        }
    }
    return res[n-1]
}

func min(a, b, c int)int{
    
    if(a < b){
    
        if a < c{
    
            return a
        }
        return c
    }
    if b < c{
    
        return b
    }
    return c
}

The first 60 topic

//  Make f(n,s) It's a two-dimensional matrix , Expressed as n The number of dice is s The situation of 
func dicesProbability(n int) []float64 {
    
	dp := make([][]int32, 0)        // Build a n+1 That's ok ,n*6+1 Array of columns . among +1 It is convenient to handle the boundary .
    for i := 0;i < n+1;i ++{
    
        tt := make([]int32, n*6+1)
        dp = append(dp, tt)
    }
	res := make([]float64, 5*n+1)   // preservation n The result of a dice 
	allSituation := math.Pow(6, float64(n))     //  The number of occurrences saved in the array , So calculate the total number of times to calculate the probability 
	for j := 1; j <= 6; j++ {
    
		dp[1][j] = 1
	}
	for i := 1; i <= n; i++ {
           // i A dice 
		for j := i; j <= n*6; j++ {
         // And for j
			for k := 1; k <= 6; k++ {
          // f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)
				if j >= k {
    
					dp[i][j] += dp[i-1][j-k]
				}
				if i == n {
    
					res[j-i] = float64(dp[i][j]) / allSituation
				}
			}
		}
	}
	return res
}