首页 > 代码库 > 两个本质相同的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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。