会社の組織と給与３

　前回にこの問題を解いたときは動的計画法を用いて解く事が出来ませんでした。そのため、今回は動的計画法を用いて解く！という目標を掲げて解いてみました。
　主な解法は前回と変わりませんが、long型配列dpを用意して、既に計算したデータ以降を枝刈り出来る様にコーディングしてみました！

public class CorporationSalary {
    long[] dp;
    String[] salaries;

    long totalSalary(String[] relations) {
        int total = 0;
        dp = new long[relations.length];
        salaries = relations;

        for(int r = 0; r < relations.length; r++) {
            total += calcSumSalary(relations[r], r);
        }
        return(total);
    }

    long calcSumSalary(String relation, int id) {
        if(dp[id] != 0) return(dp[id]);
        long total = 0;
        boolean flag = false;
        for(int r = 0; r < relation.length(); r++) {
            if(relation.charAt(r) == 'Y') {
                flag = true;
                total += (dp[r] = calcSumSalary(salaries[r], r));
            }
        }
        if(!flag) return(1);
        return(total);
    }

    void doIt() {
        String[] relations = {
                "NNYN",
                "NNYN",
                "NNNN",
                "NYYN",
        };
        System.out.println(totalSalary(relations));
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new CorporationSalary().doIt();
    }

}

　ここをこう変えればもっと効率化出来る、この書き方は良くないなどの意見を下さると大変嬉しいです！！（≧▽≦）