由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教一道切木料的DP题
相关主题
details 2nd smallest element in an arrayAmzon电面
最近连着几个面试都是印度人。8节电池 那道智力题答案是多少?
CS专业的几本书,面试用(更新完)问一道onsite算法
问一个题目,谢谢。facebook电面题目
我也来道题吧level order nodes
职业杯另外一道问一道Amazon的老题
问个sorting的题目有几个问题不明白大家能不能解答一下 谢谢!
bloomberg面经请教一道考题
相关话题的讨论汇总
话题: int话题: dp话题: cost话题: min话题: len
进入JobHunting版参与讨论
1 (共1页)
l**********g
发帖数: 16
1
请教一道DP问题,大概是这样的:
有一个长为L的木料需要割开,切的位置在一个数组里A[0...N],从一个地方切开的
cost是当前所切木料的长度。按不同的顺序切割,得到的total cost是不一样的,问怎
么切cost最
小。
我对题意的理解是,比如一个木料现在10米长,然后切的位置是2米处,4米处和7米处
(就是说arr A里A[0]是2,A[1]是4, A[2]是7)。那么比如先切2米,那么得到cost是
10(因为现在木料长度为10),然后切4米处,那么cost变成10 + 8(因为8是现在切的
时候木料的长度)。然后切7米处,cost变成10 + 8 + 6。那么这种切法总共的cost是24。
这题DP应该怎么写?递推关系是什么?谢谢!
d********i
发帖数: 582
2
代码已贴。
public static int rodCutting(int[] price, int RodLength) {
int dp[] = new int[RodLength + 1];
for (int i = 1; i <= RodLength; i++) {
for (int j = 0; j < price.length; j++) {
if (j < i) {
dp[i] = Math.max(dp[i], dp[j] + price[i - 1 - j]);
}
}
}
return dp[RodLength];
}
w****3
发帖数: 110
3
i表示计算的长度,j表示最后一切的位置,0放入index0,L放入最后一个index为编程
方便一些。比如说i=2 j=3的dp[2][3]表示楼主例子中2~7这一段的最小cost
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 2; i < a.size(); i++) {
dp[2][i] = a.get(i) - a.get(i-2);
}
for (int i = 3; i < a.size(); i++) {
for (int j = i; j < a.size(); j++) {
dp[i][j] = (a.get(j) - a.get(j-i)) + Math.min(dp[i-1][j], dp
[i-1][j-1]);
}
}
return dp[a.size()-1][a.size()-1];
}
i********5
发帖数: 52
4
你是今儿面的A吗?
l**********g
发帖数: 16
5
这个代码对这道题不work。。。对cut rob那道题应该work。。。

【在 d********i 的大作中提到】
: 代码已贴。
: public static int rodCutting(int[] price, int RodLength) {
: int dp[] = new int[RodLength + 1];
: for (int i = 1; i <= RodLength; i++) {
: for (int j = 0; j < price.length; j++) {
: if (j < i) {
: dp[i] = Math.max(dp[i], dp[j] + price[i - 1 - j]);
: }
: }
: }

l**********g
发帖数: 16
6
可能是我题意没讲清。。。我对题目的理解是:
比如还是之前的例子,但是如果第一下切4那个位置的话,首先cost = 10, 然后把木料
分成了4和6两段。然后切2那个位置,这个时候cost = 10 + 4,因为2这个位置现在位
于长度是4的这一半,然后第三下切7那里,cost = 10 + 4 + 6。那么这样切的话总
cost就是20。你的代码似乎返回的是21。。。

【在 w****3 的大作中提到】
: i表示计算的长度,j表示最后一切的位置,0放入index0,L放入最后一个index为编程
: 方便一些。比如说i=2 j=3的dp[2][3]表示楼主例子中2~7这一段的最小cost
: public int cutWood(int [] input, int L) {
: ArrayList a = new ArrayList();
: a.add(0);
: for (int i = 0; i < input.length; i++)
: a.add(input[i]);
: a.add(L);
: int [][] dp = new int [a.size()][a.size()];
: //initalize cut to 2 pieces

l**********g
发帖数: 16
7
不是。。。还在看面经的节奏。。。

【在 i********5 的大作中提到】
: 你是今儿面的A吗?
a********m
发帖数: 15480
8
不错的题目。

24。

【在 l**********g 的大作中提到】
: 请教一道DP问题,大概是这样的:
: 有一个长为L的木料需要割开,切的位置在一个数组里A[0...N],从一个地方切开的
: cost是当前所切木料的长度。按不同的顺序切割,得到的total cost是不一样的,问怎
: 么切cost最
小。
: 我对题意的理解是,比如一个木料现在10米长,然后切的位置是2米处,4米处和7米处
: (就是说arr A里A[0]是2,A[1]是4, A[2]是7)。那么比如先切2米,那么得到cost是
: 10(因为现在木料长度为10),然后切4米处,那么cost变成10 + 8(因为8是现在切的
: 时候木料的长度)。然后切7米处,cost变成10 + 8 + 6。那么这种切法总共的cost是24。
: 这题DP应该怎么写?递推关系是什么?谢谢!

E********e
发帖数: 63
9
每次切中间?greedy?
i********5
发帖数: 52
10
今天亚麻考了这道!

不是。。。还在看面经的节奏。。。

【在 l**********g 的大作中提到】
: 不是。。。还在看面经的节奏。。。
相关主题
职业杯另外一道Amzon电面
问个sorting的题目8节电池 那道智力题答案是多少?
bloomberg面经问一道onsite算法
进入JobHunting版参与讨论
l**********g
发帖数: 16
11
这么难。。。

【在 i********5 的大作中提到】
: 今天亚麻考了这道!
:
: 不是。。。还在看面经的节奏。。。

q******n
发帖数: 35
12
首先,得到每一块木头的长度,例如,楼主的例子:
L[0] = 2, L[1] = 2, L[2] = 3, L[3] = 3
然后,定义DP[i][j]为从第i块木头的左边开始切,切j块木头的最优解。
DP[i][1] = 0
DP[i][2] = L[i] + L[i+1]
DP[i][3] = L[i] + L[i+1] + L[i+2] + min (DP[i][1]+DP[i+1][2],DP[i][2]+DP[i+2
][1])
以此类推就可以了
f******n
发帖数: 279
13
mark
p********n
发帖数: 165
14
M[i][j] 记录从木头的第 i 段 到第j段 之间 的subsolution。
细节:
首先对角线上的元素(从左上到右下)都初始化0, 因为 i 到i 段不用cut,所以cost 为
0
从i,j 之间,假设我们只能cut 两个大段, 左大段和右大段,则总共有 i-j-1种cut
方法(i j之间每个可能cut的地方都试一次)
M[i][j] = A[j] - A[i] (注释:i-j之间的木头长度) +
min(M[i][i] + M[i+1][j], M[i][i+1] + M[i+2][j]), ... M[i][j-1] + M[j
][j]);
这个M矩阵,我们从下往上计算,每层从右往左计算, 只有矩阵的右上一半被计算,
左下方不管。

24。

【在 l**********g 的大作中提到】
: 请教一道DP问题,大概是这样的:
: 有一个长为L的木料需要割开,切的位置在一个数组里A[0...N],从一个地方切开的
: cost是当前所切木料的长度。按不同的顺序切割,得到的total cost是不一样的,问怎
: 么切cost最
小。
: 我对题意的理解是,比如一个木料现在10米长,然后切的位置是2米处,4米处和7米处
: (就是说arr A里A[0]是2,A[1]是4, A[2]是7)。那么比如先切2米,那么得到cost是
: 10(因为现在木料长度为10),然后切4米处,那么cost变成10 + 8(因为8是现在切的
: 时候木料的长度)。然后切7米处,cost变成10 + 8 + 6。那么这种切法总共的cost是24。
: 这题DP应该怎么写?递推关系是什么?谢谢!

l**********g
发帖数: 16
15
看起来应该work,不过我按照你的思路写了一下代码,跑我给的这个例子给出的答案是
19。。。但最小的cost应该是20?
代码如下,
public static void main(String[] args) {
int[] input = {2, 4, 7};
int L = 10;
System.out.println(cutWood(input, L));
}

public static int cutWood(int[] input, int L) {
int len = input.length;
int[] A = new int[len + 2];
A[0] = 0;
for (int i = 0; i < len; i++) {
A[i + 1] = input[i];
}
A[len + 1] = L;
int[][] M = new int[len + 2][len + 2];
for (int i = len; i >= 0; i--) {
for (int j = i + 1; j < len + 2; j++) {
M[i][j] = A[j] - A[i];
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
min = Math.min(M[i][k] + M[k + 1][j], min);
}
M[i][j] += min;
}
}
return M[0][len + 1];
}
还是说我写的这个和你的思路并不一样?。。。

[j

【在 p********n 的大作中提到】
: M[i][j] 记录从木头的第 i 段 到第j段 之间 的subsolution。
: 细节:
: 首先对角线上的元素(从左上到右下)都初始化0, 因为 i 到i 段不用cut,所以cost 为
: 0
: 从i,j 之间,假设我们只能cut 两个大段, 左大段和右大段,则总共有 i-j-1种cut
: 方法(i j之间每个可能cut的地方都试一次)
: M[i][j] = A[j] - A[i] (注释:i-j之间的木头长度) +
: min(M[i][i] + M[i+1][j], M[i][i+1] + M[i+2][j]), ... M[i][j-1] + M[j
: ][j]);
: 这个M矩阵,我们从下往上计算,每层从右往左计算, 只有矩阵的右上一半被计算,

l**********g
发帖数: 16
16
求大牛解答。。。
z******t
发帖数: 25
17
定义:
val[i]:数组A里面下标为i-1的数值,val[0]=0而val[N+1]=L
f(i,j)代表val[i]到val[j]木头段切割完的最小花销
递推公式是:
f(i,j) = min [(f(i,k) + f(k,j)) where i < k < j] + val(j) - val(i);
如果i>=j,递推无效
如果i+1==j,f返回0,因为不需要在val[i]和val[j]之间做切割
其他的就很简单了,只需要一个二维数组存中间结果,最后需要计算的是f(0,N+1)。我
就不贴代码了。
l**********g
发帖数: 16
18
感觉思路和我上面写的代码一样。。。可以麻烦看看我写的代码哪儿不对吗?谢谢!

【在 z******t 的大作中提到】
: 定义:
: val[i]:数组A里面下标为i-1的数值,val[0]=0而val[N+1]=L
: f(i,j)代表val[i]到val[j]木头段切割完的最小花销
: 递推公式是:
: f(i,j) = min [(f(i,k) + f(k,j)) where i < k < j] + val(j) - val(i);
: 如果i>=j,递推无效
: 如果i+1==j,f返回0,因为不需要在val[i]和val[j]之间做切割
: 其他的就很简单了,只需要一个二维数组存中间结果,最后需要计算的是f(0,N+1)。我
: 就不贴代码了。

o***g
发帖数: 2784
19
我就用最笨的方法。
一段木头,每个地方都切一下。每次切的时候都有左右两段。每次切的cost就是左边那
段的cost+右边的cost+整根木头的长度。所有地方都试过,然后找最小值,就是这段木
头的cost最小值了。
公式:
cost[A] = min{cost[0到i]+cost[i到n-1]+L}
好绕,下面是代码,楼主的case算出来是20
public class Solution
{
public int cutRod(int[] A, int L)
{
int result = Integer.MAX_VALUE;
int n = A.length;
if (n == 0)
{
return 0;
}
for (int i = 0; i < n; i++)
{
int[] left = new int[i];
for (int j = 0; j < i; j++)
{
left[j] = A[j];
}
int[] right = new int[n - i - 1];
for (int j = i + 1; j < n; j++)
{
right[j - i - 1] = A[j];
}
int minLeft = cutRod(left, A[i]);
int minRight = cutRod(right, L - A[i]);
result = Math.min(result, minLeft + minRight + L);
}
return result;
}
public static void main(String[] argv)
{
Solution solution = new Solution();
int[] input = new int[] { 2, 4, 7 };
System.out.println(solution.cutRod(input, 10));
}
}
H**r
发帖数: 10015
20
The first DP problem in CLRS?
相关主题
facebook电面题目有几个问题不明白大家能不能解答一下 谢谢!
level order nodes请教一道考题
问一道Amazon的老题几道MS面试题
进入JobHunting版参与讨论
x*******6
发帖数: 262
21
mark
w****3
发帖数: 110
22
是我想错了,dp的时候再加一层循环,最后return 20.复杂度似乎是n^3
其实和楼上几位的想法是一样的,先将切每段短的木料的cost算出来,每次新加一段的
时候,尝试第一刀切在这段之前的所有位置,切成两段以后的cost都已经知道了,所以
在这k个切法里找到最小的存下来即可。
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 1; i < a.size(); i++) {
dp[1][i] = 0;
}
for (int i = 2; i < a.size(); i++) {
for (int j = i; j < a.size(); j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int k = j - i + 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], a.get(j) - a.get(j-i) + dp
[k - j + i][k] + dp[j - k][j]);
}
}
}
return dp[a.size()-1][a.size()-1];
}

【在 l**********g 的大作中提到】
: 可能是我题意没讲清。。。我对题目的理解是:
: 比如还是之前的例子,但是如果第一下切4那个位置的话,首先cost = 10, 然后把木料
: 分成了4和6两段。然后切2那个位置,这个时候cost = 10 + 4,因为2这个位置现在位
: 于长度是4的这一半,然后第三下切7那里,cost = 10 + 4 + 6。那么这样切的话总
: cost就是20。你的代码似乎返回的是21。。。

s**********r
发帖数: 8153
23
这个问题我从去年就不会,一直到现在
l******n
发帖数: 577
24
弱问dp是什么。。。
k***s
发帖数: 6
25
抛迭代砖
def min_cost(self, A, L):
memory = [[0 for _ in range(len(A) + 2)] for _ in range(len(A) + 2)]

cuts = list(A)
cuts.append(0)
cuts.append(L)
cuts.sort()

for length in range(2, len(cuts)):
for start in range(0, len(cuts) - length):
min_cost = float('Inf')
fix_cost = (cuts[start + length] - cuts[start])
for i in range(start + 1, start + length):
min_cost = min(min_cost, memory[start][i] +
memory[i][start + length] + fix_cost)
memory[start][start + length] = min_cost

return memory[0][len(A) + 1]
k***s
发帖数: 6
26
抛低轨砖
def __min_cost_rec(self, cuts, start, end, memory):
if memory[start][end] is None:
fix_cost = cuts[end] - cuts[start]
min_cost = float('Inf')
for i in range(start + 1, end):
min_cost = min(min_cost,
self.__min_cost_rec(cuts, start, i, memory) +
self.__min_cost_rec(cuts, i, end, memory) +
fix_cost)
memory[start][end] = min_cost;
return memory[start][end];

def min_cost_rec(self, A, L):
memory = [[None for _ in range(len(A) + 2)] for _ in range(len(A) +
2)]
for i in range(0, len(memory) - 1):
memory[i][i + 1] = 0

cuts = list(A)
cuts.append(0)
cuts.append(L)
cuts.sort()

return self.__min_cost_rec(cuts, 0, len(cuts) - 1, memory)
f****8
发帖数: 33
27
cut[][] = new int[][]{-1}; // cache the known best cut
start[]={0,2,4,7};
end[]={2,4,7,10};
getBestCut(from, to){
if (cut[from][to] != -1) {
return cut[from][to];
}
if (from == to)
return 0;
min = getBestCut(from + 1, to); // getBestCut(from, from) == 0.
for (i = from + 1; i < to; ++i) {
tryCut = getBestCut(from, i) + getBestCut(i + 1, to);
if (tryCut < min) min = tryCut;
}
min += end[to] - start[from];
cut[from][to] = min;
return min;
}
本人刚刚COMPUTER ENGINEERING毕业,正在找湾区工作,求内推:f****[email protected],谢
谢!
b********r
发帖数: 620
28
this is pretty close, though you don't need to recursive call and can use a
table to store value.

【在 o***g 的大作中提到】
: 我就用最笨的方法。
: 一段木头,每个地方都切一下。每次切的时候都有左右两段。每次切的cost就是左边那
: 段的cost+右边的cost+整根木头的长度。所有地方都试过,然后找最小值,就是这段木
: 头的cost最小值了。
: 公式:
: cost[A] = min{cost[0到i]+cost[i到n-1]+L}
: 好绕,下面是代码,楼主的case算出来是20
: public class Solution
: {
: public int cutRod(int[] A, int L)

1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一道考题我也来道题吧
几道MS面试题职业杯另外一道
问道G题问个sorting的题目
问个算法题bloomberg面经
details 2nd smallest element in an arrayAmzon电面
最近连着几个面试都是印度人。8节电池 那道智力题答案是多少?
CS专业的几本书,面试用(更新完)问一道onsite算法
问一个题目,谢谢。facebook电面题目
相关话题的讨论汇总
话题: int话题: dp话题: cost话题: min话题: len