Shadek's blog

By Shadek, 8 years ago, In English

Defining proper state was the root challenge in this problem.

State can be defined by dp[a][isFulfilled]

a is current sum and isFulfilled is true/1 if we made at least one single step with length >= d.

Base Cases are:

      if(a == n && isFulfilled == 1)
      {
            return 1;
      }
     
      if(a == n && isFulfilled == 0)
      {
            return 0;
      }
      
      if(a>n)
        return 0;
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it