剑指 Offer 60. n个骰子的点数——正向递推

动态规划一般都是逆向递推，就是从结果来推理过程。这题是正向递推，从当前的数值推对后面结果的影响。

解题思路：

当前的概率是前面6个值承六分之一的和

正向递推：当前的值对后面的6个值都有影响，即相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
func dicesProbability(n int) []float64 {
    dp := []float64{(1.)/(6.),(1.)/(6.),(1.)/(6.),(1.)/(6.),(1.)/(6.),(1.)/(6.)}
    for i:=2;i<=n;i++{
        tmp := make([]float64,5*i+1)
        for j:=0; j<len(dp); j++{
            for k:=0 ; k<6;k++{
                tmp[k+j] += dp[j]*(1.)/(6.)
            }
        }
        dp = tmp
    }
    return dp
}

复杂度分析：

  • 时间复杂度$O(n^2)$
  • 空间复杂度$O(n)$

剑指 Offer 49. 丑数

每个数都必须乘2， 乘3， 乘5这样才能保证求出所有的丑数，而且还要保证丑数的顺序

设置3个索引a, b, c，分别记录前几个数已经被乘2， 乘3， 乘5了，比如a表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数；b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数；c表示前(c-1)个数都已经乘过一次5了，下次应该乘5的是第c个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func nthUglyNumber(n int) int {
    dp := make([]int,n+1)
    dp[1]=1
    a,b,c := 1,1,1
    for i:=2 ; i <=n;i++{
        n1,n2,n3 := dp[a]*2,dp[b]*3,dp[c]*5
        dp[i] = min(n1,min(n2,n3))
        if dp[i] == n1{a++}
        if dp[i] == n2{b++}
        if dp[i] == n3{c++}
    }
    return dp[n]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

1143. 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func longestCommonSubsequence(text1 string, text2 string) int {
    m,n := len(text1),len(text2)
    dp := make([][]int,m+1)
    for i,_ := range dp{
        dp[i] = make([]int,n+1)
    }

    for i:=1;i<=m;i++{
        c1 := text1[i-1]
        for j:= 1;j<=n;j++{
            c2 := text2[j-1]
            if c1 == c2{
                dp[i][j] = dp[i-1][j-1] + 1
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}
func max(a,b int)int{
    if a < b{
        return b
    }else{
        return a
    }
}