蓝桥杯2022年第十三届省赛真题-李白打酒加强版（动态规划简单易懂-Java）

解题思路: 看代码即可有注解
注意事项: 

参考代码:

import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException{

        String[] s = reader.readLine().split(" ");
		int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
		
		/*
		状态表示：
		    f(i, j, k) 表示 看遇到了i次花 j次店 时还剩k斗酒 的所有方案的集合
		    属性：存储计数（遇到了i次花 j次店 时还剩k斗酒的所有方案数的数量）
		状态计算：
		    f(i, j, k) 分两种情况 一种 是我这一步是遇到了花 另一种情况是遇到了店
		    （1）遇到了花 需要消耗一斗酒：
		            f(i, j, k) = f(i - 1, j, k + 1) 那么得出 k + 1 <= m --> k < m
		    （2）遇到了店 酒的斗数需要加倍：
		            f(i, j, k) = f(i, j - 1, k / 2) 得出只有k为偶数时才有意义
		*/
		int mod = (int)1e9 + 7;
		//最多喝m次酒故每次剩余的斗数也不会大于m
		int[][][] f = new int[m + 1][n + 1][m + 1];
		//初始化1 只遇到了花
		f[0][0][2] = 1;
		f[1][0][1] = 1;
		f[2][0][0] = 1;
		//初始化2 只遇到了店（k超出m就没有意义了）
		for(int i = 1; i <= n && Math.pow(2, (i + 1)) <= m; i++) {
		    f[0][i][(int)Math.pow(2, (i + 1))] = 1; 
		}
		for(int i = 1; i <= m; i++) {
		    for(int j = 1; j <= n; j++) {
		        for(int k = 0; k <= m; k++){
		            //上面分析的两种情况
		            if(k < m) {
		                f[i][j][k] += f[i - 1][j][k + 1];
		            }
		            if(k % 2 == 0) {
		                f[i][j][k] += f[i][j - 1][k / 2];
		            }
		            f[i][j][k] %= mod;
		        }
		    }
		}
        
		//因为没有表示具体的状态，f(m, n, 0)有可能是以看到店结束的，因为如果之前酒就是0斗那么最后也可以是0斗结束
		//所以f(m, n, 0)无法区分状态
		//转化一下思路 f(m, n, 0)想要以看花结束0斗状态 那么显然f(m - 1, n, 1)符合答案要求，输出即可。
		//PS：有错误欢迎指出！
		log.write(f[m - 1][n][1] + " ");
		
		// 释放资源
        reader.close();
        log.flush();
        log.close();
	}
}