Project Euler/158

We consider strings of n <= 26 diff chars from the alphabet.

For every n, p(n) is the number of strings of length n for which exactly one character comes lexicographically AFTER its neighbour to the left.

What is the maximum value of p(n)?

Overview of approach

For a string of length n, we can compute p(n) via

$ C_{n} = C_{n-1} + 2^{n-1} - 1 $

$ P(n) = \binom{26}{n} C_{n} $

The recurrence suggests a recursive or dynamic approach might work.

Code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round5_150-160/158

$ cat Problem158.java
public class Problem158 {
	public static void main(String[] args) {
		System.out.println(solve());
	}

	public static int pow(int b, int p) {
		int result = b;
		for(int i=2; i<=p; i++) {
			result *= b;
		}
		return result;
	}

	public static String solve() {
		int m = 26;
		BinomialDP b = new BinomialDP(m);

		long p = 0;
		long priorconfigs = 1;
		for(int n=3; n<=26; n++) {

			long binom = (long)( b.binomial(26,n) );
			long configs = (long)(priorconfigs + (pow(2,n-1)-1));
			long pnew = binom*configs;

			//System.out.printf("%12d\t%12d\t%12d\t%12d\n",n,binom,configs,pnew);

			p = Math.max(p,pnew);
			priorconfigs = configs;
		}
		return Long.toString(p);
	}
}