AcWing 900. 整数划分-代码注释-算法描述-golang
原题链接
简单
作者:
望哥
,
2020-07-25 16:15:57
,
所有人可见
,
阅读 845
package main
import (
"bufio"
"fmt"
"os"
)
const (
N = 1010
Mod = int(1e9 + 7)
)
var reader = bufio.NewReader(os.Stdin)
var writer = bufio.NewWriter(os.Stdout)
var n int
// - **计数类DP**: 整数划分, 一个正整数n可以表示成若干个正整数之和,形如:`n=n1+n2+…+nk`,其中`k≥1`。。
// 第一种定义方式, 类似背包问题:
// - 状态定义:
// - 集合: `dp[i][j]` 表示 利用 `1~i` 之间的数恰好构造出j的所有方案
// - 属性: 方案数量
// - 状态计算: `dp[i][j] = dp[i-1][j] + dp[i][j-i]`,
// - 不选择i: 即利用 `1 ~ i-1` 之间的数构造j, 即 `dp[i-1][j]`
// - 选择i: 目标数j扣除一个i 即 `j-i`, 即利用 `1 ~ i` 之间的数构造 `j-i`, 即 `dp[i][j-i]`
// - 状态计算一维化: `dp[i][j]`只利用到了 `dp[i-1][j]` 为上一行同位置,`dp[i][j-i]` 为同一行前面位置, 可一维化 `dp[j] = dp[j] + dp[j-i]`, 循环优先计算更小索引的数值。
var dp [N]int
func solution1() int{
dp[0] = 1 // 不选择任何数
for i:=1;i<=n;i++{
for j:=i;j<=n;j++ {
dp[j] = (dp[j] + dp[j-i]) % Mod
}
}
return dp[n]
}
//
// 第二种定义方式:
// - 状态定义:
// - 集合: `dp[i][j]` 表示 总数为i,恰好是j个数的和所有方案
// - 属性: 方案数量
// - 状态计算: `dp[i][j] = dp[i-1][j-1] + dp[i-j][j]`,
// - j个数中最小值是1: 这种情况的方案数和 目标数i减一,个数j减一是一样的,即 `dp[i-1][j-1]`
// - j个数中最小值大于1: 这种情况将j个数每个都减去1,则目标数减去了j,其方案数是一样的,即 `dp[i-j][j]`
// - 最终的总方案数是加总 `sum(dp[n][1~n])`
var f [N][N]int
func solution2() int{
f[0][0] = 1
for i:=1;i<=n;i++ {
for j:=1;j<=i;j++{
f[i][j] = (f[i-1][j-1] + f[i-j][j]) % Mod
}
}
res:=0
for i:=1;i<=n;i++{
res= (res+f[n][i]) % Mod
}
return res
}
func main() {
fmt.Fscan(reader, &n)
fmt.Println(solution1())
//fmt.Println(solution2())
}