JS: DP 棒切割。重复不会超过 "for cycle" 中的 i = 1

Question

我在理解循环 "for" 和循环如何一起工作时遇到了一些困难。我试图在Java脚本中实现切杆问题。（原代码写在Java）。

问题： 问题是循环在每个循环 i = 1 中下降到底部，直到它达到最低值，但它不会执行下一个循环 i = 2。这段代码有什么问题？

代码：

var p = [2,5,8,9,10,17,17,20,24,30];
function cut_rod(p,n){
        console.log("           level=",n); 
        if(n == 0){
            return 0;
        } 
        q = Number.MIN_VALUE;

        for(i = 1; i <= n; i++){
            console.log("           i=",i);
            q = Math.max(q, p[i-1] + cut_rod(p, n-i));
            console.log("           q=",q);         
        }         
        return q;
}
console.log(cut_rod(p,10));

当我决定实现只执行每个循环的每个步骤的循环时遇到了同样的问题。（只是为了理解递归，没有解决一些问题）

代码：

function test(sum){
    console.log("i'm here sum",sum);
    if (sum < 1) {
        console.log("       ",sum," is less then 1, return",1);
        return x=1;
    }
    else{
        for(i=1;i<=3;i++){
            console.log("           i=",i);
            x = test(sum-i)+1;
            console.log("           x=",x)
        }       
    }
    return x;
} 

console.log("----------------->start"); 
console.log("answer",test(5));

非常感谢。

Answer 1

这是范围问题。您的 i 和 q 变量是 global 变量，而不是 local 变量。

将for(i = 1; i <= n; i++){ ...更改为for(var i = 1; i <= n; i++){ ...

和q = Number.MIN_VALUE;到var q = Number.MIN_VALUE;。

Answer 2

我写了这段代码：

cutRod = function(p, n) {
    if (n === 0)
        return 0;
    var q = -Infinity;
    for (var i = 1; i < n; i++)
        q = Math.max(q, p[i] + cutRod(p, n - i - 1));
    return q;
};

arr = [1, 5, 8, 10, 13, 17, 18, 22, 25, 30];
debug("Maximum obtainable value is " + cutRod(arr, 5));

看第 5 行 for 循环条件是 i < n.
在第 6 行，递归调用 cutRod 的第二个参数是 n - i - 1.
尝试在您的代码中进行此调整，看看它是否有效。

JS: DP 棒切割。重复不会超过 "for cycle" 中的 i = 1

JS: DP rod cutting . A recurrence doesn't go further than i = 1 in "for cycle"

javascript

algorithm

recurrence

dynamic-programming