#14

// fibmemo.c --- calcurate fib with memoization.
#include <stdio.h>
#include <stdlib.h>
#define ARRSIZE 100
int fib(int n) {
  if(n <= 1) { return 1; }
  return fib(n-1) + fib(n-2);
}
int fib1(int n) {
  static int memo[ARRSIZE];
  if(memo[n] != 0) { return memo[n]; }
  int r = 1;
  if(n > 1) { r = fib1(n-1) + fib1(n-2); }
  memo[n] = r; return r;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  printf("fib(%d) = %d\n", n, fib1(n));
  return 0;
}

int pow3(n) {
  if(n <= 0) { return 1; }
  return pow3(n-1) + pow3(n-1) + pow3(n-1);
}

int fact(int n) {
  if(n <= 1) { return 1; }
  int r = 0;
  for(int i = 0; i < n; ++i) { r += fact(n-1); }
  return r;
}

int comb(int n, int r) {
  if(r == 0 || r == n) { return 1; }
  return comb(n, r-1) + comb(n-1, r-1);
}

// fibdp.c --- calcurate fib with dynamic progrmming.
#include <stdio.h>
#include <stdlib.h>
#define ARRSIZE 100
static unsigned memo[ARRSIZE];
void initfib() {
  memo[0] = memo[1] = 1;
  for(int i = 2; i < ARRSIZE; ++i) { memo[i] = memo[i-1]+memo[i-2]; }
}
unsigned fib2(int n) { return memo[n]; }
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]); initfib(); 
  printf("fib(%d) = %u\n", n, fib2(n));
  return 0;
}

// numpath1.c --- number of paths using DP.
#include <stdio.h>
#define W 8
#define H 6
static int map[H][W];
int main(void) {
  for(int i = 0; i < W; ++i) { map[0][i] = 1; }
  for(int j = 0; j < H; ++j) { map[j][0] = 1; }
  for(int i = 1; i < W; ++i) {
    for(int j = 1; j < H; ++j) {
      map[j][i] = map[j][i-1] + map[j-1][i];
    }
  }
  printf("%d\n", map[H-1][W-1]);
  return 0;
}

// lcs.c --- longest common sequence length for two strings.
#include <stdio.h>
#include <string.h>
#define MAXSTR 50
static int a[MAXSTR][MAXSTR];
int lcs(char *s1, char *s2) {
  int l1 = strlen(s1), l2 = strlen(s2);
  for(int i = 0; i <= l1; ++i) { a[0][i] = 0; }
  for(int j = 0; j <= l2; ++j) { a[j][0] = 0; }
  for(int j = 1; j <= l2; ++j) {
    for(int i = 1; i <= l1; ++i) {
      int m = a[j][i-1];
      if(m < a[j-1][i]) { m = a[j-1][i]; }
      if(s1[i-1] == s2[j-1] && m < a[j-1][i-1]+1) { m = a[j-1][i-1]+1; }
      a[j][i] = m;
    }
  }
//for(int j = 0; j <= l2; ++j) {
//  for(int i = 0; i <= l1; ++i) { printf("%3d", a[j][i]); }
//  printf("\n");
//}
  return a[l2][l1];
}
int main(int argc, char *argv[]) {
  char *s1 = argv[1], *s2 = argv[2];
  printf("lcs(%s,%s) = %d\n", s1, s2, lcs(s1, s2));
  return 0;
}