Riešenia (skupina D, 7.-8. týždeň)

import java.util.Arrays;

public class Tester {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] p = new int[] { 5, 3, 1, 4, 6, 2, 8, 7 };
                System.out.println("Dlzka najdhlsej vybranej rastucej podpostupnosti je: "+NVRP(p));
        }

        // Najdlhšia vybraná rastúca podpostupnosť
        public static int NVRP(int[] p) {

                // pole medzivysledkov, ktore naplnam
                int[] d = new int[p.length];

                // maximalna dlzka podpostupnosti
                int maxDlzka = 0;

                for (int i = 0; i < p.length; i++) {
                        d[i] = 1;
                        for (int j = 0; j < i; j++)

                                // ak i-ty prvok je mensi nez j-ty, tak ho mozem prilepit k NVRP
                                // konciatej v j-tom prvku
                                if (p[j] < p[i]) {
                                        d[i] = Math.max(d[i], d[j] + 1);
                                        if (d[i] > maxDlzka)
                                                maxDlzka = d[i];
                                }
                }

                // pre kontrolu vypis pole medzivysledkov
                System.out.println(Arrays.toString(d));

                return maxDlzka;
        }

}

import java.util.Arrays;

public class Tester {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[][] pole = new int[5][5];

//              for (int i = 1; i < pole.length; i++) {
//                      for (int j = 1; j < pole.length; j++) {
//                              pole[i][j] = (int) (Math.random() * 10);
//
//                      }
//                      System.out.println(Arrays.toString(pole[i]));
//              }
//
//              System.out.println(zberJablk(pole));
                System.out.println(vypocitajLCS("ABBACA", "ABCA"));
        }

        public static int zberJablk(int[][] pole) {
                int[][] pozbieraneJ = new int[pole.length][pole.length];
                for (int i = 1; i < pole.length; i++) {
                        for (int j = 1; j < pole.length; j++) {
                                pozbieraneJ[i][j] = Math.max(pozbieraneJ[i - 1][j],
                                                pozbieraneJ[i][j - 1]) + pole[i][j];
                        }
                }
                return pozbieraneJ[pozbieraneJ.length - 1][pozbieraneJ.length - 1];
        }

        public static int vypocitajLCS(String s1, String s2) {
                int[][] lcs = new int[s1.length() + 1][s2.length() + 1];
                for (int i = 1; i < s1.length() + 1; i++) {
                        for (int j = 1; j < s2.length() + 1; j++)
                                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                                        lcs[i][j] = 1 + lcs[i - 1][j - 1];
                                else
                                        lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                System.out.println(Arrays.toString(lcs[i-1]));
                }
                System.out.println(Arrays.toString(lcs[lcs.length-1]));
                return lcs[s1.length()][s2.length()];
        }
}

import java.util.Arrays;

public class Bankovky {
        public static int pocetMinci(int hodnota, int[] mince) {
                int[] vysledky = new int[hodnota + 1];
                for (int i = 0; i < mince.length; i++) {
                        vysledky[mince[i]] = 1;
                }

                for (int i = 1; i < vysledky.length; i++) {
                        if (vysledky[i] == 0)
                                vysledky[i] = Integer.MAX_VALUE;
                        for (int j = 0; j < mince.length; j++) {
                                if (i - mince[j] > 0)
                                        vysledky[i] = Math.min(vysledky[i],
                                                        vysledky[i - mince[j]] + 1);
                        }
                }
                System.out.println(Arrays.toString(vysledky));
                return vysledky[vysledky.length - 1];
        }

        public static void main(String[] args) {
                int[] mince = { 1, 2, 5, 10 };
                System.out.println(pocetMinci(13, mince));
        }

public static boolean daSaVyplatit(int suma) {
                int poI = mince.length;
                boolean[] vysledky = new boolean[suma + 1];
                if (poI == 0 && suma != 0)
                        return false;
                if (suma == 0)
                        return true; // else return false;
                if (suma < 0)
                        return false;
                for (int i = 0; i < mince.length; i++) {

                        int t = mince[i];
                        mince[i] = 0;
                        poI--;
                        if (daSaVyplatit(suma - mince[i]))
                                return true;
                        mince[i] = t;
                        poI++;
                }

                return false;
        }