📣 独立日限时特惠: VIP通行证立减$68
楼主: AmyZhu
跳转到指定楼层
上一主题 下一主题
收起左侧

狗狗店面

🔗
stzy 2018-11-10 18:03:18 来自APP | 只看该作者
全局:
每个数字可以重复用吗?比如S=6时(3,3)算一个结果吗?
回复

使用道具 举报

🔗
大木虫 2018-11-10 22:52:42 | 只看该作者
全局:
求组合数的话,用二维DP

评分

参与人数 1大米 +5 收起 理由
dengzeyu147 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
monaziyi 2018-11-10 23:13:35 | 只看该作者
全局:
wofaint 发表于 2018-11-10 17:41
问的就是组合数,不是所有组合

看错了, DP靠谱
回复

使用道具 举报

🔗
dengzeyu147 2018-11-11 00:41:04 | 只看该作者
全局:
大木虫 发表于 2018-11-10 22:52
求组合数的话,用二维DP

求个转移方程式子 谢谢大佬
回复

使用道具 举报

🔗
大木虫 2018-11-11 01:27:42 | 只看该作者
全局:
dengzeyu147 发表于 2018-11-11 00:41
求个转移方程式子 谢谢大佬

我是这样想的,你看对不对
一个N 一个S,N是要用的数字的数量,S是目标和
转移可以从T(N-1, S-i)开始,0 <= i <= S
例如,T(5, 3) = T(4, 0) + T(4, 1) + T(4, 2) + T(4, 3)
T(4, 0)的每一个子答案添一个3 构成T(5, 3)一个子集
T(4, 1)的每一个子答案添一个2 构成T(5, 3)一个子集
T(4, 2)的每一个子答案添一个1 构成T(5, 3)一个子集
T(4, 3)的每一个子答案添一个0 构成T(5, 3)一个子集
合起来就是T(5, 3)

我感觉这题应该有公式解,找找规律没准能找出来。

评分

参与人数 5大米 +17 收起 理由
weiduanxu8 + 1 赞一个
huieewu + 5 T(N,S) = \SUM_{0 &lt;= i &lt;= S} T(N-1,
AmyZhu + 5 给你点个赞!
dengzeyu147 + 5 很有用的信息!
stzy + 1 赞一个

查看全部评分

回复

使用道具 举报

全局:
AmyZhu 发表于 2018-11-9 12:18
由0...N的意思,比如N=5, 就是求(0,1,2,3,4,5)这里面所有组合加起来等于S。

那楼主你自己举的例子就错了吧?你说N = 2 S = 5,那就是求(0,1,2)这里面所有组合加起来等于5  组合数是多少呢?很混乱
回复

使用道具 举报

🔗
dengzeyu147 2018-11-11 03:15:37 | 只看该作者
全局:
EbyccoCheng 发表于 2018-11-10 00:30
从0-s间选n个数字 加起来等于s
可以用dp吧
sum(加起来等于s-i的n-1个数字的方式)

大佬能给个转移方程吗?
回复

使用道具 举报

🔗
monaziyi 2018-11-11 04:01:12 | 只看该作者
全局:
stzy 发表于 2018-11-10 18:03
每个数字可以重复用吗?比如S=6时(3,3)算一个结果吗?

应该都可以吧, 唯一区别就是dfs时是否包含当前值
回复

使用道具 举报

🔗
vividlau 2018-11-11 04:53:32 | 只看该作者
全局:
dfs + memorize 吧,容易想到也好讲清楚
回复

使用道具 举报

🔗
 楼主| AmyZhu 2018-11-11 06:43:59 | 只看该作者
全局:
找工作啊找工作 发表于 2018-11-11 01:53
那楼主你自己举的例子就错了吧?你说N = 2 S = 5,那就是求(0,1,2)这里面所有组合加起来等于5  组合数 ...

抱歉,之前例子举得有问题。N就是说最后要的组合长度。比如N=3的话,S还是5,那么(0, 1, 4)就是一个有效的组合。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表