AlgoClub_57.md

Задачі - http://codegym.in.ua/courses/3

Ланцюжок

import java.util.*;

public class Solution {

  public static int[] results ;

  public static int count(int N) {
    if (N <= 0) return 0;
    if(results[N] > 0) return results[N];

 int res = count(N-1) + count(N-2) + count(N-3);
 results[N] = res;
 return res;
   }

   public static void main(String[] args) {
     Scanner in = new Scanner(System.in);
     int N = in.nextInt();
     results = new int[Math.max(N+1, 4)];
     results[1] = 1;
     results[2] = 2;
     results[3] = 4;
     count(N);

     System.out.println(results[N]);
   }


 }

Фібоначчі

import edu.princeton.cs.algs4.Stopwatch;

public class Fibonacci {

  public static void main(String[] args) {
    Stopwatch stopwatch = new Stopwatch();

    System.out.println(fib2(100));

    System.out.printf("Time : %.3f sec", stopwatch.elapsedTime());

  }

  public static int fib2(int N) {
    int result = 1;
    int prev = 1;
    int prev2 = 1;

    for (int i = 3; i <= N; i++) {
      result = prev2 + prev;
      prev2 = prev;
      prev = result;
    }

    return result;
  }

 public static int fib(int N) {
   if (N <= 2) return 1;

   return fib(N-1) + fib(N-2);
 }

}

Алгоритм Грабіжника

import java.util.*;

public class Solution { 
  public static void main(String[] args) { 
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int [] houses = new int[N];
    int [] results = new int[N];
 
     for(int i = 0; i <N; i++){
       houses[i] = in.nextInt();
     } 
     results[0] = houses[0];
     results[1] = Math.max(houses[0], houses[1]);
     for(int i = 2; i < N; i++){
       results[i] = Math.max(houses[i]+results[i-2], results[i-1]);
         
     } 
       
     System.out.println(results[N-1]);
   } 
 }