如何用java动态规划实现话说大诗人李白,一生好饮。 幸好他从不开车。 一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。 他边走边唱: 无事街上走,提壶去打酒。 逢店加一倍,遇花喝一斗。 这一路上,他一共遇到店 N 次,遇到花 M 次。 已知最后一次遇到的是花,他正好把酒喝光了。 请你计算李白这一路遇到店和花的顺序,有多少种不同的可能? 注意:壶里没酒 (0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。 输入格式 第一行包含两个整数 N 和 M。 输出格式 输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果。 数据范围 对于 40% 的评测用例:1≤N,M≤10。 对于 100% 的评测用例:1≤N,M≤100。 输入样例: 5 10 输出样例: 14
时间: 2023-02-16 16:51:40 浏览: 47
动态规划需要确定状态和状态转移方程。
在这个问题中,可以定义状态 dp[i][j] 表示李白遇到了 i 家店,喝了 j 斗酒的方案数。
然后可以得到状态转移方程:
dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]
第一项表示李白在这家店加倍,第二项表示李白在这家店喝了一斗酒。
但是要注意,李白喝了酒后不能再遇到花,所以需要特判:
if (j == 0) {
dp[i][j] = dp[i-1][j+1];
}
然后,最后一次遇到的是花,所以最终答案是 dp[N][0]。
以下是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][2] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i-1][j+1];
if (j > 0) {
dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
}
}
}
System.out.println(dp[n][0]);
}
}
```