DP

1. 계단 오르기

package com.codingtest.Algorithm.Chapter10.DP;

import java.util.Scanner;

public class 계단오르기 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int stairs = in.nextInt();

        System.out.println(cntNum(stairs));
    }

    private static int cntNum(int stair) {

      if (stair == 1 || stair == 0) {
        return 1;
      }
        return cntNum(stair - 1) + cntNum(stair - 2);
    }

}

2. 돌다리 건너기

package com.codingtest.Algorithm.Chapter10.DP;

import java.util.Scanner;

public class 돌다리_건너기 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int stairs = in.nextInt();

        System.out.println(cntNum(stairs + 1));
    }

    private static int cntNum(int stair) {

      if (stair == 1 || stair == 0) {
        return 1;
      }
        return cntNum(stair - 1) + cntNum(stair - 2);
    }
}

3. 최대 부분 증가 수열

package com.codingtest.Algorithm.Chapter10.DP;

import java.util.Arrays;
import java.util.Scanner;

public class 최대_부분_증가수열 {

    public static int[] dy;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        String[] strArr = s.split(" ");

        int answer = 0;

        int[] arr = Arrays.stream(strArr)
            .mapToInt(Integer::parseInt)
            .toArray();
        dy = new int[arr.length];
        dy[0] = 1;

        for (int i = 1; i < arr.length; i++) {
            int max = 0;
            for (int j = i - 1; j >= 0; j--) {
              if (arr[j] < arr[i] && dy[j] > max) {
                max = dy[j];
              }
            }
            dy[i] = max + 1;
            answer = Math.max(answer, dy[i]);
        }
        System.out.println(answer);
    }
}

실수한 부분

s = s.replaceAll(" ", "");
    int[] arr = Arrays.stream(s.split(""))
        .mapToInt(Integer::parseInt)
        .toArray();

4. 가장 높은 탑 쌓기

package com.codingtest.Algorithm.Chapter3.DP;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class 가장_높은_탑_쌓기 {

    static int[] dy;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        ArrayList<Brick> arr = new ArrayList<>();
        dy = new int[num];

        for (int i = 0; i < num; i++) {
            int s = in.nextInt();
            int h = in.nextInt();
            int w = in.nextInt();
            arr.add(new Brick(s, h, w));
        }

        System.out.println(getMaxHeight(arr));
    }

    public static int getMaxHeight(ArrayList<Brick> arr) {
        int answer = 0;
        Collections.sort(arr);
        dy[0] = arr.get(0).h;
        answer = dy[0];

        for (int i = 1; i < arr.size(); i++) { //dy
            int max_h = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (arr.get(j).w > arr.get(i).w && dy[j] > max_h) {
                    max_h = dy[j];
                }
            }
            dy[i] = max_h + arr.get(i).h;
            answer = Math.max(answer, dy[i]);
        }

        return answer;
    }

    public static class Brick implements Comparable<Brick> {

        public int s, h, w;

        Brick(int s, int h, int w) {
            this.s = s;
            this.h = h;
            this.w = w;
        }

        @Override
        public int compareTo(Brick o) {
            return o.s - this.s;
        }

    }
}

5. 동전교환

package com.codingtest.Algorithm.Chapter3.DP;

import java.util.Arrays;
import java.util.Scanner;

public class 동전교환 {

    static int num, change;
    static int[] dy;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        num = in.nextInt();
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = in.nextInt();
        }
        change = in.nextInt();
        dy = new int[change + 1];

        System.out.println(minCoinNum(arr));
    }

    public static int minCoinNum(int[] coins) {
        Arrays.fill(dy, Integer.MAX_VALUE);
        dy[0] = 0;

        for (int i = 0; i < num; i++) {
            int coin = coins[i];
            for (int j = coin; j <= change; j++) {
                dy[j] = Math.min(dy[j - coin] + 1, dy[j]);
            }
        }

        return dy[change];
    }
}

6. 최대점수 구하기

package com.codingtest.Algorithm.Chapter10.DP;

import java.util.ArrayList;
import java.util.Scanner;

public class 최대점수_구하기 {

    static int num, totalTime;
    static int[] dy;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        num = in.nextInt();
        totalTime = in.nextInt();
        dy = new int[totalTime + 1];
        // dy[0] => 0문제 풀었을 때 최대 점수

        ArrayList<Question> arr = new ArrayList<>();

        for (int i = 0; i < num; i++) {
            int score = in.nextInt();
            int time = in.nextInt();
            arr.add(new Question(score, time));
        }

        System.out.println(getMaxScore(arr));
    }

    public static int getMaxScore(ArrayList<Question> questions) {

        for (int i = 0; i < num; i++) {
            int maxScore = 0;
            int s = questions.get(i).score;
            int t = questions.get(i).time;
            for (int j = totalTime; j >= t; j--) {
                dy[j] = Math.max(dy[j], dy[j - t] + s);
            }
        }

        return dy[totalTime];
    }

    public static class Question implements Comparable<Question> {

        public int score, time;

        Question(int score, int time) {
            this.score = score;
            this.time = time;
        }

        @Override
        public int compareTo(Question o) {
            return o.score - this.score;
        }
    }
}