ABC099 C (DP)

問題

• DPの超初歩version
• 解説見ずにこの程度は解けるようにならなくてはならない

DPについて

• DPは求める添字をnとすると1 ~ (n - 1)までの答えを知っているときに求める。
• 漸化式のようなものを作る
• 今回のような場合みたいに場合わけする必要がある場合もある。
• 動的計画法. 配列を作って添字の小さい方か大きい方かどちらかかから埋めていく。
• 配列の求める場所を別の場所を使って求めて埋めていこうというもの。

解答

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
// 配列の添字0は使わないようにする。
        int dp[] = new int[n + 1];
// 初期化する
        dp[0] = 0;
        dp[1] = 1;
// 場合分けをしていく
        for (int i = 1; i < n + 1; i++) {
            dp[i] = 1 + dp[i - 1];
            int j = 6;
            while (j <= i) {
                int tmp = 1 + dp[i - j];
                j *= 6;
                dp[i] = Math.min(dp[i], tmp);
            }
            j = 9;
            while (j <= i) {
                int tmp = 1 + dp[i - j];
                j *= 9;
                dp[i] = Math.min(dp[i], tmp);
            }
        }
        System.out.println(dp[n]);

    }
}

感想

• やっぱDPは難しい(この問題の難易度は低いはず). 漸化式というイメージが非常に重要. 前に使った要素を用いて新たな要素を作成するイメージだ!!

• もっとDPのっ問題に触れていかないとまずそう。