@Gina_Gina why three? The first one is not necessary.
yidawang
@yidawang
Posts made by yidawang

RE: Share my at most twopass constant space 10line solution

RE: Share my at most twopass constant space 10line solution
@wenzhe3 Here is the output after each iteration of the for loop.
0 1 2 0 1 2 0 2 1 2
0 1 2 0 1 2 0 2 1 2
0 1 1 0 1 2 0 2 2 2
0 0 1 1 1 2 0 2 2 2
0 0 1 1 1 2 0 2 2 2
0 0 0 1 1 1 2 2 2 2The swap will actually happen.

RE: Share my at most twopass constant space 10line solution
@wenzhe3 But it works on my side, outputting [0,0,0,1,1,1,2,2,2,2]

RE: Share my at most twopass constant space 10line solution
@Gina_Gina It works on my side. Can you elaborate?

RE: Got a wrong answer on a seemtoberight submission （Solved: be careful with the initialization!)
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[n1][n] = n1; for (int range=3; range<=n; range++) { for (int i=1; i<=nrange+1; i++) { int cur_min = INT_MAX; for (int j=i+1; j<i+range1; j++) { int candidate = j + max(dp[i][j1], dp[j+1][i+range1]); if (cur_min>candidate) cur_min = candidate; } dp[i][i+range1] = cur_min; } } return dp[1][n]; } };

Got a wrong answer on a seemtoberight submission （Solved: be careful with the initialization!)
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[n1][n] = n1; for (int range=3; range<=n; range++) { for (int i=1; i<=nrange+1; i++) { int cur_min = INT_MAX; for (int j=i+1; j<i+range1; j++) { int candidate = j + max(dp[i][j1], dp[j+1][i+range1]); if (cur_min>candidate) cur_min = candidate; } dp[i][i+range1] = cur_min; } } return dp[1][n]; } };
Specifically, the system says when
n=4
my program outputs5
, however, my program outputs4
in the "Run Code" checking beside submission.Anybody knows why? Thanks!

RE: Share my at most twopass constant space 10line solution
@FoxAtlas from the compilation perspective, I agree with you. I should modify my statement: a twopass solution could have a smaller number of total operations than a onepass solution.
Thanks so much for sharing your thought.

RE: Share my at most twopass constant space 10line solution
@FoxAtlas I understand all your points and agree that my solution is not onepass. My point is that if you count the number of operations, a twopass one could outperform a socalled onepass one.

RE: Share my at most twopass constant space 10line solution
@FoxAtlas Well, I don't think your solution is strictly onepass either. You only traverse the list once, but in each step you have multiple operations, which in the worst case is more than O(2n).

RE: Share my at most twopass constant space 10line solution
@bond1993 This algorithm goes through the list once, but at each point it could do multiple operations up to 3. As @mayijie88 said, the definitions of onepass and twopass are not clear. I can only say my algorithm is bounded by O(2n).