[アルゴリズム]白駿17213号-フルーツクリーム

質問リンク:https://www.acmicpc.net/problem/1978

質問する

民建家の果物農場ではN種の果物が栽培されている.普段から民健に恨みを抱いていた志桓は、民健を苦しめるため、民健家の果物農場から果物を盗むことを決意した.志桓は完璧な犯罪のために、最初の数だけを盗もうとした.この時志桓が盗むことができるものが何種類あるか見てみましょう.しかし、すべての種類の果物は少なくとも1つ盗まれた.

入力

1行目は果物の種類数N(1≦N≦10)を与える.
2行目は盗む果物の個数M(N≦M≦30)を与える.

しゅつりょく

1行目に盗むことができる数を出力します.

のり付け

dpを用いて解くことができる問題は,dp[i][j] += dp[i-1][1~j-1]である.二層配列リングと和を同時に求める必要があるため,三重ゲートを用いた.

コード#コード#

//https://velog.io/@cjhlsb
import java.util.*;
public class Main {
    public static void main(String[] args){
    	Scanner sc= new Scanner(System.in);
    	int n = sc.nextInt();
    	int m = sc.nextInt();
    	int[][] dp = new int[n+1][m+1];
    	for(int i=1;i<=n;i++)
    	{
    		dp[i][i] = 1;
    	}
    	for(int i=1;i<=m;i++)
    	{
    		dp[1][i] = 1;
    	}
    	for(int i=2;i<=n;i++)
    	{
    		for(int j=i+1;j<=m;j++)
    		{
    			for(int k=1;k<j;k++)
    			{
    				dp[i][j] += dp[i-1][k];
    			}
    		}
    	}
    	System.out.println(dp[n][m]);
    }
}