I don't know why it output runtime error


  • 0
    R
    class Solution {
    public:
        int dp[10000][10000];
        int MAX=1000000;
        int jump(int A[], int n)
    	{
    		if(n==0) return 0;
            for(int i=0;i<=n-1;i++)
                dp[i][i]=0;
            for(int l=2;l<=n;l++)//chain length
            {
                for(int s=0;s<=n-1;s++)//start indx
                {
                    int e=s+l-1;
    				if(e>n-1)
    					break;
                    if(A[s]>=l-1)//min 1
                        dp[s][e]=1;
                    else
                    {
                        int min=MAX;
                        for(int k=s+1;k<=e-1;k++)
                        {
                            if(min>dp[s][k]+dp[k][e])
                                min=dp[s][k]+dp[k][e];
                        }
                        dp[s][e]=min;
                    }
                }
            }
            return dp[0][n-1];
        }
    };
    

    The wrong case is [0], but I think it is 0 when only one element in the array, as it does not need to jump, and the first is also the last index, and my code will definitely return 0 if only one element? Does it mean it should not return 0 when only one element? Also I want to make sure that all cases will have a solution to jump to the end index.


  • 0
    R

    I know the reason, maybe it is because dp is too large, I try heap space but it exceed memory space...


  • 0
    S

    The problem may be solved with dp, but it is not the optimal solution. There exists a greedy solution that runs in O(n) time and O(1) space. You may want to take a look at other posts for this question.


Log in to reply
 

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