腾讯的一道算法题,该怎么处理
腾讯的一道算法题
给定n个数字和一个范围[x,y]，求从这n个数字中任意取出一些数字，使得它们的和在范围[x,y]中有多少种取法。
这个思路应该是什么呢？
------解决方案--------------------
有看到这一种解法，数组劈两半，两边各自枚举，过滤掉不符合条件的元素，比如该元素加上另一半的的和还打不到x，或者本身大于y。枚举完之后然后对另一半排序，对于第一部分的每个元素，在第二部分二分查找满足条件的开始元素位置和结束元素位置，累计。
------解决方案--------------------
被1楼启发，动态规划是这样的，假如有数k1,k2,k3, ... k(n-1),kn
kn这个数，只有两种选择，选或者不选，选的话，问题转化为k1,k2,k3,...,k(n-1),在[x-kn,y-kn]里的和，不选的话，问题变成k1,k2,k3,...,k(n-1)，在[x,y]里的和。
------解决方案--------------------
可以看做0-1背包问题。f[i][j]=f[i-1][j]+f[i-1][j-x[i]] j>=x[i]-x
f[i][j]=f[i-1][j]j<x[i]-x
------解决方案--------------------
DP解0-1背包，当你=y的数量求出来的时候，x(<y)的数量也都出来了
给定n个数字和一个范围[x,y]，求从这n个数字中任意取出一些数字，使得它们的和在范围[x,y]中有多少种取法。
这个思路应该是什么呢？
------解决方案--------------------
有看到这一种解法，数组劈两半，两边各自枚举，过滤掉不符合条件的元素，比如该元素加上另一半的的和还打不到x，或者本身大于y。枚举完之后然后对另一半排序，对于第一部分的每个元素，在第二部分二分查找满足条件的开始元素位置和结束元素位置，累计。
------解决方案--------------------
被1楼启发，动态规划是这样的，假如有数k1,k2,k3, ... k(n-1),kn
kn这个数，只有两种选择，选或者不选，选的话，问题转化为k1,k2,k3,...,k(n-1),在[x-kn,y-kn]里的和，不选的话，问题变成k1,k2,k3,...,k(n-1)，在[x,y]里的和。
------解决方案--------------------
可以看做0-1背包问题。f[i][j]=f[i-1][j]+f[i-1][j-x[i]] j>=x[i]-x
f[i][j]=f[i-1][j]j<x[i]-x
------解决方案--------------------
DP解0-1背包，当你=y的数量求出来的时候，x(<y)的数量也都出来了