C++ DP Solution


  • 0
    Q

    I examined every case and it yield the correct answer. But the system yield the wrong answer and I do not know why.
    For example, My solution output 108 when the parameter is 13. But the leetcode system says my program output 355923. I have no idea about this issue

    class Solution {
    public:
        int integerBreak(int n) {
            int *dp = new int[n+1];
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 1;
            for(int i=3;i<=n;i++){
                for(int j=1;j<i;j++){
                    int t1 = max(dp[j]*dp[i-j],dp[j]*(i-j));
                    int t2 = max(j*dp[i-j],j*(i-j));
                    int t3 = max(t1,t2);
                    dp[i] = max(dp[i],t3);
    
                }
            }
            
            return dp[n];
        }
    };
    

  • 0
    W

    I guess you just need to initialize the dp array to all 0, otherwise, the default value can be undefined, can be pretty large, so it is not updated by your algorithm. thus give wrong answer


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.