动态规划 -- 整数划分 - (sunznx) 振翅飞翔
27 October 2019

整数划分:

一个正整数 n 可以表示成若干个正整数之和,形如: n=n1+n2+…+nk, 其中 n1≥n2≥…≥nk,k≥1 ,求 n 共有多少种不同的划分方法

例如,数字 5 可以有如下划分方式:

5

1 4
2 3

1 1 3
1 2 2

1 1 1 2

1 1 1 1 1

因此,数字 5 的划分方式有 1+2+2+1+1=7

将 n 划分成 k 个数的划分法

dp[n][k] 表示整数 n 可由 k 个数组组成,则可以将 dp[n][k] 分成两个集合:

  1. k 个数中,至少有一个数含有 1
  2. k 个数中,所有的数字都不是 1

分别计算上面两个集合。

集合 1

计算集合 1 的时候,可以把数字 1 从集合中拿掉,那么就变成了 dp[n-1][k-1]

例如:
dp[9][3] 中含有 1 的集合如下

1 1 7
1 2 6
1 3 5
1 4 4

dp[8][2] 的集合如下(注意和 dp[9][3] 是一一对应的)

1 7
2 6
3 5
4 4

集合 2

计算集合 2 的时候,可以把所有的数字都减去 1,那么就变成了 dp[n-k][k]

例如:
dp[9][3] 中,所有的数字都不是 1 的集合如下

2 2 5
2 3 4
3 3 3

dp[6][3] 的集合如下(注意和 dp[9][3] 是一一对应的)

1 1 4
1 2 3
2 2 2

总结

因此 dp[n][k]=dp[n-k][k]+dp[n-1][k-1]

将 n 划分成最大数不超过 m 的划分法(可以存在相同数)

dp[n][m] 表示对整数 n 进行划分时,所有数的最大数不超过 m,则可以将 dp[n][m] 分成两个集合:

  1. 所有的数都比 m 小
  2. 存在至少一个数,值为 m

分别计算上面两个集合。

集合 1

直接是 dp[n][m-1]

集合 2

计算集合 2 的时候,首先将 n-m ,得出除去一个 m 后,还剩多少需要划分的,因为剩下的数里面还有可能存在 m 。因此集合 2 的推导式是 dp[n-m][m]

总结

dp[n][m]=dp[n][m-1]+dp[n-m][m]

将 n 划分成最大数不超过 m 的划分法(不存在相同数)

dp[n][m] 表示对整数 n 进行划分时,所有数的最大数不超过 m,则可以将 dp[n][m] 分成两个集合:

  1. 所有的数都比 m 小
  2. 存在一个数,值为 m

分别计算上面两个集合。

集合 1

直接是 dp[n][m-1]

集合 2

计算集合 2 的时候,首先将 n-m ,得出除去一个 m 后,还剩多少需要划分的,因为剩下的数里面还有不可能存在 m 。因此集合 2 的推导式是 dp[n-m][m-1]

总结

dp[n][m]=dp[n][m-1]+dp[n-m][m-1]

将 n 划分成若干奇数的划分法

g[n][k] 表示将 n 划分为 j 个偶数, f[n][j] 表示将 n 划分为 j 个奇数,则

因为奇数和偶数是一一对应的,那么有:

  1. g[n][j]f[n+j][j] 是一一对应的
  2. f[n][j]g[n+j][j] 是一一对应的
  3. g[n][j]f[n-j][j] 是一一对应的
  4. f[n][j]g[n-j][j] 不是一一对应的

因为遍历的时候是从小到大的顺序,因此 1 和 2 在这里不做考虑。解释下 4 为什么不是一一对应的:
假设奇数集合为 {3,5,9} ,那么我们能找到 {2,4,8} 与之对应。但是奇数集合为 {1,5,9} 这种含有 1 的集合,我们不能转成 {0,4,8} ,因为数字肯定是 >=1

因此, f[n][j] 可以分为两个集合:

  1. 集合中含有 1
    f[n-1][j-1]
  2. 集合中没有 1
    g[n-j][j]

因此,有 f[n][j]=f[n-1][j-1]+g[n-j][j]