CareerCup

What's a scoring sequence? I think I may know what kind of thing you're talking about. Is this problem akin to "If a basketball team scored 80 points in a game, how many scoring sequences of 2 or 3 points are possible?" In this case, the answer would be F(n) = F (n-2) + F(n-3), subject to base cases of F(2) = F(3) = 1 and F(1) = 0.

I start by thinking of it as a coin problem - given a total amount, how many different ways can you get that amount? So the 'score' is the amount, and the points are the coin values.

For example, if score was s=100, and points were either {3, 5, 7} the minimum number of shots scored would be 16 (7x13 + 3x3). You can work backwards from there to find all other possible combinations of shots that would result in a score of 100.

For each individual combination of shots, you then have to multiply by the different ways those shots could be ordered. For example, all thirteen 7 pointers followed by the three 3 pointers, etc.

This is calculated by [total shots]! / [score-count-1]![score-count-2]!... so, there are 16!/13!3! or 560 different ways you could make thirteen 7-pointers and three 3-pointers.

Can you give some example???

#define SIZE 3
int tab[SIZE]={4, 10, 15};
int score=80;

int f(s)
{
  printf(" %d", s);
  if(s<0) 
  {
    printf(" nope\n");
    return(0);
  }
  else
  if(!s)
  {
    printf(" found\n");
    return(1);
  }
  else
  {
    return(f(s-tab[0]) || f(s-tab[1]) || f(s-tab[2]));
  }
}

The lines ending with found is the results

answer(x) = 2^x
EOF

answer(x) = 2^x
EOF

// example
// f(4)
//
// 1 1 1 1
// 2 1 1
// 1 2 1
// 1 1 2
// 2 2
// 3 1
// 1 3
// 4

public static void main(String[] args) {
    assert getSeqCount(4) == 8;
    assert getSeqCount2(4) == 8;
}

/**
 * DP (quadratic)
 */
private static int getSeqCount2(int n) {
    int[] dp = new int[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i < dp.length; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j];
        }
    }
    return dp[n];
}

/**
 * naive recursive (exponential)
 */
private static int getSeqCount(int n) {
    if (n <= 1) {
        return 1;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int newN = n - i;
        if (newN >= 0) {
            res += getSeqCount(newN);
        }
    }
    return res;
}

bool is_bst(struct Node * node) {
return (node->left == NULL && node->right == NULL) ||
(
(node->left == NULL || (node->left->value<=node->value && is_bst(node->left)
&&
(node->right == NULL || (node->right->value>=node->value && is_bst(node->right);
);
}