首页 > 代码库 > 两个本质相同的dp

两个本质相同的dp


1.划分数
描述:给定数字N,将其划分为不超过K组,求不同的划分的总数(比如4——1 2 1,2 1 1就算做一种划分)

2.Dollar Dayz
描述:给定数字N,将其随意划分,但是组成数字不可以超过K,求不同的划分总数。

这两者看起来是有不同的。

比如对于N=100 K=30的情况。

第一个不可能出现100个1的组成,但是第二个却完全可以。

那么:

对于第一个:
设方程dp[n][k]是n不超过k的划分,有
dp[n][k]=
dp[n][k-1]+ (假如划分份数不为k)
dp[n-k][k] (假如划分份数为k,那么划分的每一个数都减去1,就是n-k的k划分——n是必定>=k的)

对于第二个:
设方程dp[n][k]是数字n包含可能的最大划分单元为k的答案。
dp[n][k]=
dp[n][k-1]+ (假如最大的单元不是K,这部分等同于dp[n][k-1])
dp[n-k][k] (假如最大的单元是K,这部分等同于N减去这个单元划分就是dp[n-k][k])

方程完全一样。
但是含义是不同的。
问题的性质也是不同的(我觉得)

我不相信巧合——
所以是不是这两个问题,其实在本质上存在着共性?

两个本质相同的dp