如何用java实现话说大诗人李白,一生好饮。 幸好他从不开车。 一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。 他边走边唱: 无事街上走,提壶去打酒。 逢店加一倍,遇花喝一斗。 这一路上,他一共遇到店 N 次,遇到花 M 次。 已知最后一次遇到的是花,他正好把酒喝光了。 请你计算李白这一路遇到店和花的顺序,有多少种不同的可能? 注意:壶里没酒 (0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。 输入格式 第一行包含两个整数 N 和 M。 输出格式 输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果。 数据范围 对于 40% 的评测用例:1≤N,M≤10。 对于 100% 的评测用例:1≤N,M≤100。 输入样例: 5 10 输出样例: 14
时间: 2023-02-05 07:29:40 浏览: 45
你可以使用动态规划的思想来解决这道题。
首先,定义状态 $dp[i][j]$ 表示已经遇到了 $i$ 次店和 $j$ 次花时的方案数。
其次,考虑状态转移方程。在遇到店时,可以选择加倍或不加倍,因此 $dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$。在遇到花时,只能选择喝酒,因此 $dp[i][j]=dp[i][j-1]$。
最后,由于在遇到花之前必须要有酒,所以 $dp[0][j]=0$。
因此,最终的状态转移方程为:
$$
dp[i][j]=
\begin{cases}
dp[i-1][j]+dp[i-1][j-1] & i \neq 0 \\
dp[i][j-1] & i=0
\end{cases}
$$
最后,答案即为 $dp[N][M]$。
下面是 Java 代码:
```
import java.util.Scanner;
public class Main {
static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
sc.close();
int[][] dp = new int[N + 1][M + 1];
dp[0][0] = 1;
for (int i = 0; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (i > 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
} else {
dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
}
}
}
System.out.println(dp[N][M]);
}
}
```