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 | |
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 | |
i********5 发帖数: 52 | 10 今天亚麻考了这道!
不是。。。还在看面经的节奏。。。
【在 l**********g 的大作中提到】 : 不是。。。还在看面经的节奏。。。
|
|
|
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 | |
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 | |
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? |
|
|
x*******6 发帖数: 262 | |
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 | |
l******n 发帖数: 577 | |
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)
|