波波老师，Integer Break问题的动态规划解法中求memo[i]的时候为什么还要和memo[i]自己比较

Question

for(int i = 2;i <= n;i++){

    for(int j = 1;j <= i - 1;j++){

        memory[i] = max3(memory[i],j * (i - j),j * memory[i - j]);

    }

}

Answer 1

liuyubobobo 2018-07-29 14:51:03

在内层循环中，对于每一个当下的j，j*(i-j)是指把i分成两个数j和i-j得到的结果；j * memo[i - j])指的是把i分成多于两个数（至少三个数），其中有一个数字为j的结果。可以看出，这两个情况都至少有一个数字为j。但是memo[i]中存储的最优值，可能并没有一个数字j。所以，要将以前获得的memo[i]的最优值，和当下，考虑某一个具体的j时得到的最优值比较，选取最好的结果：）