Count number of ways to reach a given score in a game

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of ways to reach the given score.

Examples:

Input: n = 20
Output: 4

Count Possible Decodings of a given Digit Sequence

Find number of ways a string can be decoded into, if A=1, B=2, C=3 ... Z=25 and encoding number is 123 ways decoding can be done is
1 2 3 = A B C
1 23  = A X
12 3  = L C

Word Break Problem

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.

Consider the following dictionary 
{ i, like, go, hired, gohired, site, sweet,fruit, man, go, mango}

Input:  ilike
Output: Yes 
The string can be segmented as "i like".

Input:  ilikemango
Output: Yes
The string can be segmented as "i like mango" or "i like man go".

Longest Increasing Subsequence

The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, length of LIS for { 3,2,6,4,5,1 } is 2 and LIS is {2,4,5}.