一、
大富翁游戏，玩家根据骰子的点数决定走的步数，即骰子点数为1时可以走一步，点数为2时可以走两步，点数为n时可以走n步。求玩家走到第n步（n<=骰子最大点数且是方法的唯一入参）时，总共有多少种投骰子的方法。
输入描述:
输入包括一个整数n,(1 ≤ n ≤ 6)
输出描述:
输出一个整数,表示投骰子的方法
示例1
输入
6
输出
32
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
/* 一开始想用动态规划，结果发现更简单的办法，所以不用总是一来就动态规划
* f(n)=f(n-1)+...+f(1)+1 ①
* f(n-1)=f(n-2)+...+f(1)+1 ②
* ②-①得到f(n)=f(n-1)*2
*/
System.out.println((int)Math.pow(2, n - 1));
}
sc.close();
}
}二
给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。
输入描述:
输入包括一个整数n(1 ≤ n ≤ 10000)
输出描述:
输出一个整数,表示不同的组合方案数
示例1
输入
1
输出
1
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
/*背包问题
只用第一种面额时，装入背包都只有一种方式
当使用前两种面额时，装满背包除了原来的方式外，还可以用新的面额组合
*/
while(sc.hasNext()) {
int n = sc.nextInt();
int money[]={1, 5, 10, 20, 50, 100};//dp看做背包的容量
long[]dp = new long[n+1];
//--------------------初始化-----------------------
dp[0] = 1;
//----------------------规划-----------------------
for(int i = 0; i < 6; i++){//money[i]看做物品重量
for(int j=money[i];j<=n;j++){
dp[j] += dp[j-money[i]];
}
}
System.out.println(dp[n]);
}
sc.close();
}
}三、
给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积。 入参h为一个整型数组，代表每个柱子的高度，返回面积的值。
输入描述:
输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000)
第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)
输出描述:
输出一个整数,表示最大的矩阵面积。
示例1
输入
6
2 1 5 6 2 3
输出
10
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Stack<Integer> stk = new Stack<>();
stk.add(0);
int i = 1, max = a[0];
while(i <= n) {//i作为矩形右边界
if(i == n && !stk.isEmpty()) {
int j = stk.pop();
max = Math.max(max, a[j] * (stk.isEmpty()?i:i-stk.peek()-1));
}else {
if(stk.isEmpty()||a[i]>=a[stk.peek()]){//找局部峰值
stk.add(i++);
}else{
int j=stk.pop();
max=Math.max(max, a[j]*(stk.isEmpty()?i:i-stk.peek()-1));
}
}
}
System.out.println(max);
}
sc.close();
}
}四、
给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。
输入描述:
输入为两行字符串（可能包含空格），长度均小于等于50.
输出描述:
输出为一个整数，表示最长公共连续子串的长度。
输入
abcde
abgde
输出
2
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s1=sc.nextLine();
String s2=sc.nextLine();
sc.close();
int len1=s1.length();
int len2=s2.length();
int [][]dp=new int[len1][len2];
for(int i=0;i<len1;i++){
if(s1.charAt(i)==s2.charAt(0)){
dp[i][0]=1;
}
}
for(int i=0;i<len2;i++){
if(s2.charAt(i)==s1.charAt(0)){
dp[0][i]=1;
}
}
int max=dp[0][0];
for(int i=1;i<len1;i++){
for(int j=1;j<len2;j++){
if(s1.charAt(i)==s2.charAt(j)){
dp[i][j]=dp[i-1][j-1]+1;//dp[i][j]表示到s1的第i个字符和s2的第j个字符时，连续子串的长度
}
if(dp[i][j]>max){
max=dp[i][j];
}
}
}
System.out.println(max);
}
}