php做网站首页修改,网站建设公司广告,乌市seo网络营销流程,ui网站模板大家好#xff0c;我是晴天学长#xff0c;记忆化搜索#xff0c;找到技巧非常重要#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 2) .算法思路
1.memo三维表示记录的结果 3#xff09;.算法步骤
1…大家好我是晴天学长记忆化搜索找到技巧非常重要需要的小伙伴可以关注支持一下哦后续会继续更新的。 2) .算法思路
1.memo三维表示记录的结果 3.算法步骤
1.首先导入需要的类和包包括 java.util.Scanner。 2.创建一个公共类 Main。 3.声明一个静态变量 mod 并初始化为 1000000007用于取模操作。 4.声明一个三维数组 memo用于存储中间计算结果。 5.在 main 方法中创建一个 Scanner 对象来读取输入。 6.通过 scanner.nextInt() 方法分别读取输入的 N 和 M 的值。 7.初始化变量 sum 为 2。 8.创建大小为 101x101x101 的 memo 数组并将其所有元素初始化为 -1。 9.调用 dfs 方法并将 sum、N 和 M 作为参数传递给它。 10.在控制台打印输出 dfs 方法的返回值。 11.定义 dfs 方法接收 sum、N 和 M 作为参数。 12.首先进行递归终止条件的判断如果 sum 等于 1N 等于 0M 等于 1返回 1。 13.进行剪枝操作如果 sum 小于 0N 小于 0 或 M 小于 0返回 0。 14.如果 sum 大于 M返回 0。 15.检查 memo[sum][N][M] 是否已经计算过如果有值则直接返回该值。 16.如果没有计算过进行递归计算并将结果保存到 memo 数组中。 17.递归调用 dfs 方法传入 sum*2、N-1 和 M 作为新的参数并将结果与递归调用 dfs 方法传入 18.sum-N 和 M-1 作为新的参数的结果相加并对 mod 取模。 19.将结果保存到 memo 数组中并返回该值。 4. 代码实例
import java.util.Scanner;public class Main {static int mod 1000000007;static int[][][] memo;public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt();int M scanner.nextInt();int sum 2;memo new int[101][101][101];for (int i 0; i 101; i) {for (int j 0; j 101; j) {for (int k 0; k 101; k) {memo[i][j][k] -1; // 初始化dp数组为-1}}}System.out.println(dfs(sum, N, M));}//口枝叶回//酒喝光了遇到店是合法的,最后一次是定了的private static int dfs(int sum ,int N,int M) {if (sum1N0M1) {return 1;}//剪枝if (sum0||N0||M0) {return 0;}if (sum M) return 0;if (memo[sum][N][M]!-1) {return memo[sum][N][M];}memo[sum][N][M](dfs(sum*2, N-1, M)dfs(sum-1, N,M-1))%mod;return memo[sum][N][M];}
} 5. 总结
dp和记忆化搜索的熟练掌握。
