2021-02-23：給定一個(gè)正數(shù)n，求n的裂開方法數(shù)。規(guī)定：后面的數(shù)不能比前面的數(shù)小 。比如4的裂開方法有： 1+1+1+1、1+1+2、1+3、2+2、4，5種，所以返回5。

福哥答案2021-02-23：

自然智慧即可。
1.遞歸。有代碼。
2.動態(tài)規(guī)劃。dp是二維數(shù)組。有代碼。
3.動態(tài)規(guī)劃，空間壓縮。兩個(gè)一維數(shù)組搞定。有代碼。

代碼用golang編寫，代碼如下：

package main

import "fmt"

func main() {
    for i := 20; i < 40; i++ {
        fmt.Println(i, GetWays1(i), GetWays2(i), GetWays3(i))
    }
}

//1.遞歸
func GetWays1(n int) int {
    if n <= 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return process1(1, n)
}
func process1(startMax int, rest int) int {
    if rest == 0 {
        return 1
    }
    ans := 0
    for i := startMax; i <= rest; i++ {
        ans += process1(i, rest-i)
    }
    return ans
}

//2.動態(tài)規(guī)劃
func GetWays2(n int) int {
    if n <= 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    dp := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= n; i++ {
        dp[i][0] = 1
        dp[i][i] = 1
    }

    for startMax := n - 1; startMax >= 1; startMax-- {
        for rest := startMax + 1; rest <= n; rest++ {
            dp[startMax][rest] = dp[startMax][rest-startMax] + dp[startMax+1][rest]
        }
    }

    return dp[1][n]

}

//3.動態(tài)規(guī)劃，空間壓縮
func GetWays3(n int) int {
    if n <= 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    dp := make([][]int, 2)
    for i := 0; i < 2; i++ {
        dp[i] = make([]int, n+1)
    }
    dp[1][0] = 1
    dp[1][n] = 1
    for startMax := n - 1; startMax >= 1; startMax-- {
        dp[0][startMax] = 1
        dp[0][0] = 1
        for rest := startMax + 1; rest <= n; rest++ {
            dp[0][rest] = dp[0][rest-startMax] + dp[1][rest]
        }
        dp[1], dp[0] = dp[0], dp[1]
    }
    return dp[1][n]

}

執(zhí)行結(jié)果如下：

圖片

左神java代碼
評論