logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
NOOK HD+memory不够
avatar
NOOK HD+memory不够# PDA - 掌中宝
m*1
1 楼
有一个int类型的不重复的数组，还有一个target number，从数组中任意取出数字相加
，要求出有多少种方法可以得到这个target。比如数组{1，2}，target是5，可以是1+1
+1+1+1，也可以是1+2+2等等。 怎么用DP的思想去做啊。。另外DP题目怎么练习才好？
avatar
c*r
2 楼
With any purchase you can choose two free travel size products at checkout,
including Checks and Balances Frothy Face Wash (2.5 oz), Modern Friction (0.
5 oz), Purifying Tonic 95% Certified Organic (1.7 oz), or Starting Over Age-
erasing Moisturizer with Mimosa (0.17 oz). No code is needed, so enter
coupon code at checkout to receive free shipping with any purchase, or if
you are spending $50 ormore enter code CHECKS at checkout to receive free
shipping plus a free full size Check and Balances F
avatar
Y*a
3 楼
常只剩100MB以下，很卡顿，有解决办法吗？
avatar
p*p
4 楼
用递归的话感觉就是抽个arr[i]
然后求数组获得target - arr[i]的组合
之后合并？

+1

【在 m*****1 的大作中提到】
: 有一个int类型的不重复的数组，还有一个target number，从数组中任意取出数字相加
: ，要求出有多少种方法可以得到这个target。比如数组{1，2}，target是5，可以是1+1
: +1+1+1，也可以是1+2+2等等。 怎么用DP的思想去做啊。。另外DP题目怎么练习才好？
avatar
g*g
5 楼
不是可以插卡吗， 都转到SD卡
avatar
f*t
6 楼
leetcode上有这题吧
avatar
p*o
7 楼
lz说的内存是ram，不是internal storage

【在 g**********g 的大作中提到】
: 不是可以插卡吗， 都转到SD卡
avatar
t*h
8 楼
seems a typical dp

+1

【在 m*****1 的大作中提到】
: 有一个int类型的不重复的数组，还有一个target number，从数组中任意取出数字相加
: ，要求出有多少种方法可以得到这个target。比如数组{1，2}，target是5，可以是1+1
: +1+1+1，也可以是1+2+2等等。 怎么用DP的思想去做啊。。另外DP题目怎么练习才好？
avatar
Y*a
9 楼

谢谢，已经更正，这样写应该比较清楚

【在 p*******o 的大作中提到】
: lz说的内存是ram，不是internal storage
avatar
s*s
10 楼
题目不清楚。先说是不重复的数组，然后举的例子可以无限次的使用其中的元素。那要
是其中一个元素是0，岂不是可以有无限种。是面试官提示可以用dp的吗？题目再明确
下吧。
avatar
g*t
11 楼
屌丝的东西，要求太高了，
avatar
m*1
12 楼
噢，数组里面是没有0的，就是任意组合加起来能得到那个target，面试官没有提示。
avatar
Y*a
13 楼

有太高吗？
NOOK HD+有1GB的内存，开机后立马看running只剩不到200MB，开个Chrome马上就只剩
100MB上下

【在 g*******t 的大作中提到】
: 屌丝的东西，要求太高了，
avatar
s*n
14 楼
先sort,然后DP.这是加硬币到某数目题目的变种。
each i in range(max (arry)
c (i) = 0;
each i in arry
c[i) = 1;
然后用下面的公式开搞。
c(x) = c (x - i) + c (i)

+1

【在 m*****1 的大作中提到】
: 有一个int类型的不重复的数组，还有一个target number，从数组中任意取出数字相加
: ，要求出有多少种方法可以得到这个target。比如数组{1，2}，target是5，可以是1+1
: +1+1+1，也可以是1+2+2等等。 怎么用DP的思想去做啊。。另外DP题目怎么练习才好？
avatar
c*h
15 楼
我也很讨厌这点

★ 发自iPhone App: ChineseWeb 7.8

【在 Y**a 的大作中提到】
:
: 有太高吗？
: NOOK HD+有1GB的内存，开机后立马看running只剩不到200MB，开个Chrome马上就只剩
: 100MB上下
avatar
p*2
16 楼

DP需要sort吗？

【在 s*****n 的大作中提到】
: 先sort,然后DP.这是加硬币到某数目题目的变种。
: each i in range(max (arry)
: c (i) = 0;
: each i in arry
: c[i) = 1;
: 然后用下面的公式开搞。
: c(x) = c (x - i) + c (i)
:
: +1
avatar
Y*a
17 楼
常只剩100MB以下，很卡顿，有解决办法吗？
avatar
s*n
18 楼
好眼力，sort的确不需要。

【在 p*****2 的大作中提到】
:
: DP需要sort吗？
avatar
g*g
19 楼
不是可以插卡吗， 都转到SD卡
avatar
p*2
20 楼
val arr=Array(1,2)
val n=arr.length
var target=5
println(calPos(n,null)(target))

def calPos(i:Int, dp:Array[Int]):Array[Int]=i match{
case `n` => val ar=new Array[Int](target+1);ar(0)=1;calPos(i-1,ar)
case -1=>dp
case _ => val ar=calAmount(i,dp); calPos(i-1,ar)
}

def calAmount(i:Int,dp:Array[Int]):Array[Int]={
val ar=new Array[Int](target+1)
for(jif(jar
}
avatar
p*o
21 楼
lz说的内存是ram，不是internal storage

【在 g**********g 的大作中提到】
: 不是可以插卡吗， 都转到SD卡
avatar
g*z
22 楼
需要考虑负数吗？

+1

【在 m*****1 的大作中提到】
: 有一个int类型的不重复的数组，还有一个target number，从数组中任意取出数字相加
: ，要求出有多少种方法可以得到这个target。比如数组{1，2}，target是5，可以是1+1
: +1+1+1，也可以是1+2+2等等。 怎么用DP的思想去做啊。。另外DP题目怎么练习才好？
avatar
Y*a
23 楼

谢谢，已经更正，这样写应该比较清楚

【在 p*******o 的大作中提到】
: lz说的内存是ram，不是internal storage
avatar
w*a
24 楼
sum不考虑负数的情况：
int ways(int a[], int n, int sum)
{
int* dp = new int[sum+1];
dp[0] = 1;
for(int i = 1; i <= sum; i++)
dp[i] = 0;

for(int i = 0; i < n; i++)
for(int x = 1; x <= sum; x++)
if(x-a[i]>=0)
dp[x] = dp[x - a[i]] + dp[x];

return dp[sum];
}
avatar
g*t
25 楼
屌丝的东西，要求太高了，
avatar
e*e
26 楼
"c(x) = c (x - i) + c (i)"
是相乘吧?

【在 s*****n 的大作中提到】
: 先sort,然后DP.这是加硬币到某数目题目的变种。
: each i in range(max (arry)
: c (i) = 0;
: each i in arry
: c[i) = 1;
: 然后用下面的公式开搞。
: c(x) = c (x - i) + c (i)
:
: +1
avatar
Y*a
27 楼

有太高吗？
NOOK HD+有1GB的内存，开机后立马看running只剩不到200MB，开个Chrome马上就只剩
100MB上下

【在 g*******t 的大作中提到】
: 屌丝的东西，要求太高了，
avatar
h*6
28 楼
这题需要二维动规，排序后f(n,x)表示只使用前n个数加到x的方法数。
avatar
c*h
29 楼
我也很讨厌这点

★ 发自iPhone App: ChineseWeb 7.8

【在 Y**a 的大作中提到】
:
: 有太高吗？
: NOOK HD+有1GB的内存，开机后立马看running只剩不到200MB，开个Chrome马上就只剩
: 100MB上下
avatar
p*2
30 楼

大牛说说为什么需要排序？

【在 h**6 的大作中提到】
: 这题需要二维动规，排序后f(n,x)表示只使用前n个数加到x的方法数。
avatar
O*h
31 楼
你都开了什么service这么耗电，难道真要刷机?
avatar
h*6
32 楼
感觉上快点吧，可以写个程序验证一下。

【在 p*****2 的大作中提到】
:
: 大牛说说为什么需要排序？
avatar
d*e
33 楼
以上都是计算机盲。android是linux 系统。 free memory屁也不能说明。因为系统为
了提高性能，是能用多少内存用多少。实在不行在page 出去。

【在 O*********h 的大作中提到】
: 你都开了什么service这么耗电，难道真要刷机?
avatar
p*2
34 楼

排序前后感觉计算量都是一样吧？
n*target

【在 h**6 的大作中提到】
: 感觉上快点吧，可以写个程序验证一下。
avatar
t*a
35 楼
原生系统升最近有升级，之后有明显改善。浏览器推荐海豚。
avatar
h*6
36 楼
有道理，十二楼wangya的就是标准答案，看来我需要学习的还很多啊。

【在 p*****2 的大作中提到】
:
: 排序前后感觉计算量都是一样吧？
: n*target
avatar
p*2
37 楼

大牛也看看我的程序对不对好吗。

【在 h**6 的大作中提到】
: 有道理，十二楼wangya的就是标准答案，看来我需要学习的还很多啊。
avatar
h*6
38 楼
火星文，看不懂啊。
avatar
p*2
39 楼

看来DP转成尾递归变复杂了。哎。

【在 h**6 的大作中提到】
: 火星文，看不懂啊。
avatar
l*b
40 楼
嗯，循环好看些。数组放外面是不是就不functional了。

【在 p*****2 的大作中提到】
:
: 看来DP转成尾递归变复杂了。哎。
avatar
p*2
41 楼

循环就不是尾递归了。我是看有个帖子不知道DP怎么转换成尾递归，所以我写写的。主
要是为了尾递归。数组应该没问题，你把它看成一个大functional就可以了。里边的子
函数可以访问大函数的变量。这个没问题，不改变就可以了。

【在 l*******b 的大作中提到】
: 嗯，循环好看些。数组放外面是不是就不functional了。
avatar
m*1
42 楼
谢谢各位大哥指点，小弟醍醐灌顶，受益匪浅！
avatar
e*e
43 楼
大牛能说说动态规划的方程末？

【在 w****a 的大作中提到】
: sum不考虑负数的情况：
: int ways(int a[], int n, int sum)
: {
: int* dp = new int[sum+1];
: dp[0] = 1;
: for(int i = 1; i <= sum; i++)
: dp[i] = 0;
:
: for(int i = 0; i < n; i++)
: for(int x = 1; x <= sum; x++)
avatar
l*b
44 楼
en, right

【在 p*****2 的大作中提到】
:
: 循环就不是尾递归了。我是看有个帖子不知道DP怎么转换成尾递归，所以我写写的。主
: 要是为了尾递归。数组应该没问题，你把它看成一个大functional就可以了。里边的子
: 函数可以访问大函数的变量。这个没问题，不改变就可以了。
avatar
p*2
45 楼

其实很简单，就是对于某种硬币来说只有最多两个选择
1. 取0个
2. 取一个
如果不够取一个，就只能取0个了。

【在 e****e 的大作中提到】
: 大牛能说说动态规划的方程末？
avatar
g*s
46 楼
回去重看＂背包问题九讲＂的多重背包的优化。好像是第三讲。

【在 p*****2 的大作中提到】
:
: 其实很简单，就是对于某种硬币来说只有最多两个选择
: 1. 取0个
: 2. 取一个
: 如果不够取一个，就只能取0个了。
avatar
p*2
47 楼

你的意思还是需要排序？

【在 g***s 的大作中提到】
: 回去重看＂背包问题九讲＂的多重背包的优化。好像是第三讲。
avatar
g*s
48 楼
是的。否则 ｛１，2,１，１。。。。。。１｝这样的例子过不去。

【在 p*****2 的大作中提到】
:
: 你的意思还是需要排序？
avatar
p*2
49 楼

有一个int类型的不重复的数组

【在 g***s 的大作中提到】
: 是的。否则 ｛１，2,１，１。。。。。。１｝这样的例子过不去。
avatar
g*s
50 楼
哦。 呵呵，没看到这个

★ 发自iPhone App: ChineseWeb 7.7

【在 p*****2 的大作中提到】
:
: 有一个int类型的不重复的数组
avatar
e*e
51 楼
谢二爷指点，但是这道题，除了取0个，1个，还可以取多个。公式c(x) = c(x - i) +
c(i)我觉得也不对.

【在 p*****2 的大作中提到】
:
: 有一个int类型的不重复的数组
avatar
e*e
52 楼
回答自己的问题.
T(i, j) represents the num of ways in which, the sum is j by adding up any
array elements indexed between 0 and ith any num of times.
T(i, j) = / T( i-1, j ) + T( i, j - a[i] ) if j >= a[i]
\ T( i-1, j ) else

临界值
T(i, j) 1 i = j = 0
0 else
avatar
p*2
53 楼

+
不需要管那么多，取一个就可以了。剩下的已经算好了。

【在 e****e 的大作中提到】
: 谢二爷指点，但是这道题，除了取0个，1个，还可以取多个。公式c(x) = c(x - i) +
: c(i)我觉得也不对.
avatar
e*e
54 楼
是的。公式我从wangya贴的代码里推出来了...详见我的上一个回贴.

【在 p*****2 的大作中提到】
:
: +
: 不需要管那么多，取一个就可以了。剩下的已经算好了。
avatar
h*g
55 楼
不管序号的话，你的算法会不会把 2+1+2=5算两遍？
T(2)+T(3)=T(3)+T(2)
1+1+1+1+1=5呢？
另外，为什么不是T(i)*T(n-i)，二是T(i)+T(n-i)?我糊涂了...

【在 p*****2 的大作中提到】
:
: +
: 不需要管那么多，取一个就可以了。剩下的已经算好了。
avatar
e*e
56 楼
看我34楼的回贴，这个公式c(x) = c(x - i) + c(i)不对。

【在 h********g 的大作中提到】
: 不管序号的话，你的算法会不会把 2+1+2=5算两遍？
: T(2)+T(3)=T(3)+T(2)
: 1+1+1+1+1=5呢？
: 另外，为什么不是T(i)*T(n-i)，二是T(i)+T(n-i)?我糊涂了...
avatar
h*g
57 楼
明白了，wangya 计算的相当于是 c[x]=sum_i{T(x,i)}, i=0,...,n-1
T(x,i) 如你的定义。

【在 e****e 的大作中提到】
: 看我34楼的回贴，这个公式c(x) = c(x - i) + c(i)不对。
avatar
e*e
58 楼
是吧。wangya代码里按照我的定义表示是T(i, x)，就是对每一个a[i]都算一遍T。这里
wangya用了一个一维数组，实际是空间优化的结果，未优化之前，可以用二维数组。

【在 h********g 的大作中提到】
: 明白了，wangya 计算的相当于是 c[x]=sum_i{T(x,i)}, i=0,...,n-1
: T(x,i) 如你的定义。
相关阅读
小米盒子无线安装app这些电视/游戏盒子最傻的就是没和手机 app 结合最近回国，有啥值得搬运过来的？拚了微軟取消手機授權金包子求助，N5不亮了Official Windows Phone 8.1 change log看你们讨论mozilla的问题，庆幸自己没有与果轮为伍有谁给三星的S3换过屏呀？有没有带DVR功能的盒子？目前域名续费哪家代理最便宜？ipad hdmi接电视看youtube全屏Lumia Icon 是WP的精品买个亚马逊机顶盒吧不用对马迅电视盒子长草了。为什么laptop长时间不用的话要50%电池保存？最需要开发盒子的是netflix乐视盒子C1S 中国互联网电视连接失败智能筷子S5 $700发现 airport extreme 经常掉线，用过的来看一下
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。