狗狗店面

非常友好的国人大哥。

题目挺简单的，就是我一直卡一直卡，说明水平还是不行。。大哥一直提示我，太感动了。

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

做的不太好，以为跪了，下午就收到过了的消息。。在准备Onsite，求RP。。。

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)

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

EbyccoCheng 发表于 2018-11-10 00:30
从0-s间选n个数字 加起来等于s
可以用dp吧
sum（加起来等于s-i的n-1个数字的方式）

dp只能求出组合数，题目要求返回所有的组合，感觉还是dfs合适

组合的dfs吧 lz加油！我也是电面有一块卡住没写出来还给的onsite 现在已经过了hc啦 好好刷题！

所有组合的方式n，是什么意思啊？是说一共n个数，总和为s吗？

思路应该是nSum，给的list是range(0, S)

从0-s间选n个数字 加起来等于s
可以用dp吧
sum（加起来等于s-i的n-1个数字的方式）

国人大叔真不错，恭喜楼主

sala510 发表于 2018-11-9 23:31
所有组合的方式n，是什么意思啊？是说一共n个数，总和为s吗？

由0...N的意思，比如N=5, 就是求(0,1,2,3,4,5)这里面所有组合加起来等于S。

paratrooper979 发表于 2018-11-10 00:20
组合的dfs吧 lz加油！我也是电面有一块卡住没写出来还给的onsite 现在已经过了hc啦 好好刷题！

谢谢鼓励！好羡慕！！真棒！！！

monaziyi 发表于 2018-11-10 01:35
dp只能求出组合数，题目要求返回所有的组合，感觉还是dfs合适

问的就是组合数，不是所有组合