Got a wrong answer on a seem-to-be-right submission (Solved: be careful with the initialization!)


  • 0
    Y

    My following solution runs well locally but got a wrong answer in the submission system.

    class Solution {
    public:
        int getMoneyAmount(int n) {
            int dp[n+1][n+1];
            for (int i=1; i<n; i++) {
                dp[i][i] = 0;
                dp[i][i+1] = i;
            }
            dp[n-1][n] = n-1;
            for (int range=3; range<=n; range++) {
                for (int i=1; i<=n-range+1; i++) {
                    int cur_min = INT_MAX;
                    for (int j=i+1; j<i+range-1; j++) {
                        int candidate = j + max(dp[i][j-1], dp[j+1][i+range-1]);
                        if (cur_min>candidate) cur_min = candidate;
                    }
                    dp[i][i+range-1] = cur_min;
                }
            }
            return dp[1][n];
        }
    };
    

    Specifically, the system says when n=4 my program outputs 5, however, my program outputs 4 in the "Run Code" checking beside submission.

    Anybody knows why? Thanks!


  • 0
    Y

    Never mind. I figured out the reason. I forgot to initialize dp[n][n], which obviously is not automatically set to 0 in the submission system. The auto initialized values are DIFFERENT between the submission system and the "Run code" test!!! Don't forget to correctly initialize the variables.

    So the correct solution is as follows, the missing line was dp[n][n] = 0;

    class Solution {
    public:
        int getMoneyAmount(int n) {
            int dp[n+1][n+1];
            for (int i=1; i<n; i++) {
                dp[i][i] = 0;
                dp[i][i+1] = i;
            }
            dp[n][n] = 0;
            dp[n-1][n] = n-1;
            for (int range=3; range<=n; range++) {
                for (int i=1; i<=n-range+1; i++) {
                    int cur_min = INT_MAX;
                    for (int j=i+1; j<i+range-1; j++) {
                        int candidate = j + max(dp[i][j-1], dp[j+1][i+range-1]);
                        if (cur_min>candidate) cur_min = candidate;
                    }
                    dp[i][i+range-1] = cur_min;
                }
            }
            return dp[1][n];
        }
    };
    

Log in to reply
 

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