本文主要是介绍ural 1017. Staircases DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1017. Staircases
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
One curious child has a set of N little bricks (5 ≤ N ≤ 500). From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:
Your task is to write a program that reads the number N and writes the only number Q — amount of different staircases that can be built from exactly N bricks.
Input
Number N
Output
Number Q
Sample
| input | output |
|---|---|
212 | 995645335 |
Problem Source: Ural State University Internal Contest '99 #2
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out);long[][] dp = new long[501][501] ;long dfs(int n , int m){if(n < 0 || m < 0){return 0 ; }if(n == 0){return 1 ;}if(dp[n][m] != -1){return dp[n][m] ;}return dp[n][m] = dfs(n-m, m-1) + dfs(n,m-1) ;}void solve() {for(int i = 0 ; i <= 500 ; i++){Arrays.fill(dp[i] , -1) ;}int n = in.nextInt() ;out.println(dfs(n , n )-1) ;out.flush();}}class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = new StringTokenizer(""); } private void eat(String s) { tokenizer = new StringTokenizer(s); } public String nextLine() { try { return reader.readLine(); } catch (Exception e) { return null; } } public boolean hasNext() { while (!tokenizer.hasMoreTokens()) { String s = nextLine(); if (s == null) return false; eat(s); } return true; } public String next() { hasNext(); return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public int[] nextInts(int n){ int[] nums = new int[n] ; for(int i = 0 ; i < n ; i++){ nums[i] = nextInt() ; } return nums ; } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public BigInteger nextBigInteger() { return new BigInteger(next()); } } 这篇关于ural 1017. Staircases DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
