初始化int maxValue=Integer有什么好处.动态编程中的MIN_VALUE

Question

为了准确地问您这个问题，初始化int max_val=Integer有什么好处。MIN_VALUE over int max_val=价格[i-1]？

这似乎是一个微不足道的DP问题。但是，我需要你的帮助。一般DP问题从初始化max_val为Integer开始。最小值。我知道这是一种标准的方式。

但是，我发现将max_val设置为price[I-1]并没有错。

例如，我得到22，arr＝｛1 5 8 9 10 17 17 20｝，cutRod(arr，8(。

我得到了24，arr＝｛3 5 8 9 10 17 17 20｝，cutRod(arr，8(。

public class RodCutting {
public static void main(String[] args) {
int[] arr = new int[] {2, 5, 13, 19, 20};
int size = arr.length;
int result = cutRod(arr, size);
System.out.println("Maximum Obtainable Value is " + result);
}
private static int cutRod(int[] price, int n) {
int val[] = new int[n+1];
val[0] = 0;
for (int i = 1; i <= n; i++) {
int max_val = price[i-1]; // previously, int max_val = Integer.MIN_VALUE;
for (int j = 0; j < i; j++) 
max_val = Math.max(max_val,  val[j+1]+ val[i - j - 1]); 
// previously, max_val = Math.max(max_val, price[j] + val[i - j - 1]);
val[i] = max_val;
}
return val[n];
}
}

提前谢谢。

Answer 1

在一般意义上，没有强大的"优点"；将局部变量初始化为CCD_ 1。。。相对于保证小于或等于您正在计算的最大值的任何其他值。

在这种情况下，这种调整显然对计算复杂性没有影响。您仍然需要执行内部循环j - i次。它可能会影响Math.max调用内部的分支，但我怀疑性能差异是否会显著。。。无论哪种方式，唯一可以确定的方法是使用一组具有代表性的大量样本进行仔细的基准测试。这只会给你一个解决这个特殊问题的答案。

但是，您知道Integer.MIN_VALUE必须小于或等于实际最大值。因此，使用这个值意味着在正确性证明中需要证明的东西少了一件。(或者换一种说法，它可能会让你的代码更容易理解。(

---

但事情是这样的。如果你要尝试这样的调整，你应该自己推理。。。不寻求经验的"；优点"；，或者请别人为你做推理。如果您这样做是出于性能原因，那么也应该进行基准测试。

如果工作量太大。。。接受Knuth关于过早优化的建议。