保山网站建设报价,智慧团建密码只能是8位吗,磁县邯郸网站建设,wordpress二级分类目录目录
最暴力的dfs -- 记忆化搜索 --- 递推(dp)
记忆化搜索 暴力dfs 记录答案
递推的公式 dfs 向下递归的公式
递推数组的初始值 递归的边界
动态规划(dp)入门 | 这tm才是入门动态规划的正确方式! | dfs记忆化搜索 | 全体起立!!_哔哩哔哩_bilibili 大佬教学视频…目录
最暴力的dfs -- 记忆化搜索 --- 递推(dp)
记忆化搜索 暴力dfs 记录答案
递推的公式 dfs 向下递归的公式
递推数组的初始值 递归的边界
动态规划(dp)入门 | 这tm才是入门动态规划的正确方式! | dfs记忆化搜索 | 全体起立!!_哔哩哔哩_bilibili 大佬教学视频非常细 题目一大盗阿福
题目描述
输入格式输入的第一行是一个整数 T表示一共有 T 组数据。接下来的每组数据第一行是一个整数 N 表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。
输出格式对于每组数据输出一行。该行包含一个整数表示阿福在不惊动警察的情况下可以得到的现金数量。 题目分析
题目代码1——最暴力的dfs 题目代码 2——记忆化搜索模板
记忆化搜索 暴力dfs 记录答案
题目代码3——递推(dp)
递推的公式 dfs 向下递归的公式递推数组的初始值 递归的边界 题目代码4——递推(dp)
空间优化
第二题数字三角形
输入格式
输出格式
输入输出样例
说明/提示
题目代码1——最暴力的dfs 题目代码 2——记忆化搜索模板
记忆化搜索 暴力dfs 记录答案
题目代码3——递推(dp)
递推的公式 dfs 向下递归的公式递推数组的初始值 递归的边界 第三题01背包问题
题目代码1——最暴力的dfs
题目代码 2——记忆化搜索模板
记忆化搜索 暴力dfs 记录答案 题目代码3——递推(dp)
递推的公式 dfs 向下递归的公式递推数组的初始值 递归的边界 最暴力的dfs -- 记忆化搜索 --- 递推(dp) 记忆化搜索 暴力dfs 记录答案 递推的公式 dfs 向下递归的公式 递推数组的初始值 递归的边界 动态规划(dp)入门 | 这tm才是入门动态规划的正确方式! | dfs记忆化搜索 | 全体起立!!_哔哩哔哩_bilibili 大佬教学视频非常细 题目一大盗阿福 题目描述 阿福是一名经验丰富的大盗。趁着月黑风高阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺每家店中都有一些现金。 阿福事先调查得知只有当他同时洗劫了两家相邻的店铺时街上的报警系统才会启动然后警察就会蜂拥而至。 作为一向谨慎作案的大盗阿福不愿意冒着被警察追捕的风险行窃。 他想知道在不惊动警察的情况下他今晚最多可以得到多少现金 输入格式 输入的第一行是一个整数 T表示一共有 T 组数据。 接下来的每组数据第一行是一个整数 N 表示一共有 N 家店铺。 第二行是 N 个被空格分开的正整数表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。 输出格式 对于每组数据输出一行。该行包含一个整数表示阿福在不惊动警察的情况下可以得到的现金数量。 输入样例 2 3 1 8 2 4 10 7 6 14 输出样例 8 24 数据范围 T ≤ 50 1 ≤ N ≤ 105 提示 对于第一组样例阿福选择第 2 家店铺行窃获得的现金数量为 8。 对于第二组样例阿福选择第 1 和 4 家店铺行窃获得的现金数量为 10 14 24。 题目分析 最暴力的dfs -- 记忆化搜索 --- 递推(dp) 题目代码1——最暴力的dfs import java.util.Arrays;
import java.util.Scanner;public class 大盗阿福_dp {static int t, n;static int arr[] new int[106];static int mem[] new int[106];public static void main(String[] args) {Scanner sca new Scanner(System.in);t sca.nextInt();while (t-- 0) {n sca.nextInt();for (int i 1; i n; i) {arr[i] sca.nextInt();}System.out.println(dfs(1));}}static int dfs(int x) {//x:表示当前正在考虑哪家店if (x n) return 0;else return Math.max(dfs(x 1), dfs(x 2) arr[x]);}
}题目代码 2——记忆化搜索模板 记忆化搜索 暴力dfs 记录答案 import java.util.Arrays;
import java.util.Scanner;public class 大盗阿福_dp {static int t, n;static int arr[] new int[106];static int mem[] new int[106];public static void main(String[] args) {Scanner sca new Scanner(System.in);t sca.nextInt();while (t-- 0) {n sca.nextInt();for (int i 1; i n; i) {arr[i] sca.nextInt();}Arrays.fill(mem,0);//每一组记忆化前都要赋值为0System.out.println(dfs(1));}}//mem[i]存的是从第i家店铺开始i~n能洗劫到的最大价值static int dfs(int x) {if (mem[x] ! 0) return mem[x];//记忆化搜索int sum 0;if (x n) sum 0;else sum Math.max(dfs(x 1), dfs(x 2) arr[x]);mem[x] sum;return sum;}
}题目代码3——递推(dp) 递推的公式 dfs 向下递归的公式递推数组的初始值 递归的边界 import java.util.Arrays;
import java.util.Scanner;public class 大盗阿福_dp {static int t, n;static int arr[] new int[106];static int mem[] new int[106];public static void main(String[] args) {Scanner sca new Scanner(System.in);t sca.nextInt();while (t-- 0) {n sca.nextInt();for (int i 1; i n; i) {arr[i] sca.nextInt();}for (int i n; i 0; i--) {mem[i] Math.max(mem[i1], mem[i2] arr[i]);}System.out.println(mem[1]);}}
}题目代码4——递推(dp) 空间优化 import java.util.Arrays;
import java.util.Scanner;public class 大盗阿福_dp {static int t, n;static int arr[] new int[106];static int mem[] new int[106];public static void main(String[] args) {Scanner sca new Scanner(System.in);t sca.nextInt();while (t-- 0) {n sca.nextInt();for (int i 1; i n; i) {arr[i] sca.nextInt();}int sum0, temp1 0, temp2 0;for (int i 1; i n; i) {sum Math.max(temp1, temp2 arr[i]);temp2 temp1;temp1 sum;}System.out.println(sum);}}
}第二题数字三角形 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4
4 5 2 6 5 在上面的样例中,从 7→3→8→7→5 的路径产生了最大 输入格式 第一个行一个正整数 r ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 输出格式 单独的一行,包含那个可能得到的最大的和。 输入输出样例 输入 #1复制 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 输出 #1复制 30说明/提示 【数据范围】 对于 100% 的数据1≤r≤1000所有输入在[0,100] 范围内。 题目代码1——最暴力的dfs import java.util.Scanner;public class 数字三角形_dp1 {static int n;static int map[][];public static void main(String[] args) {Scanner sca new Scanner(System.in);n sca.nextInt();map new int[n 1][n 1];for (int i 1; i n; i) {for (int j 1; j i; j) {map[i][j] sca.nextInt();}}System.out.println(dfs(1, 1));}static int dfs(int x, int y) {if (x n || y n) return 0;else return Math.max(dfs(x 1, y), dfs(x 1, y 1)) map[x][y];}
}题目代码 2——记忆化搜索模板 记忆化搜索 暴力dfs 记录答案 import java.util.Scanner;public class 数字三角形_dp1 {static int n;static int map[][];static int mem[][];public static void main(String[] args) {Scanner sca new Scanner(System.in);n sca.nextInt();map new int[1005][1005];mem new int[1005][1005];for (int i 1; i n; i) {for (int j 1; j i; j) {map[i][j] sca.nextInt();}}System.out.println(dfs(1, 1));}static int dfs(int x, int y) {if (mem[x][y] 0) return mem[x][y];int sum 0;if (x n || y n) sum 0;else sum Math.max(dfs(x 1, y), dfs(x 1, y 1)) map[x][y];mem[x][y] sum;return sum;}
}题目代码3——递推(dp) 递推的公式 dfs 向下递归的公式递推数组的初始值 递归的边界 import java.util.Scanner;public class 数字三角形_dp2 {static int n;static int map[][];static int dp[][];public static void main(String[] args) {Scanner sca new Scanner(System.in);n sca.nextInt();map new int[1005][1005];dp new int[1005][1005];for (int i 1; i n; i) {for (int j 1; j i; j) {map[i][j] sca.nextInt();}}for (int i n; i 1; i--) {//反着推for (int j 1; j n; j) {//j是从1开始dp[i][j] Math.max(dp[i 1][j], dp[i 1][j 1]) map[i][j];}}System.out.println(dp[1][1]);}
}第三题01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi价值是 wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤1000 0vi,wi≤1000 输入样例 4 5
1 2
2 4
3 4
4 5输出样例 8题目代码1——最暴力的dfs import java.util.Scanner;public class _01背包问题_dp1 {static int n, m,res0;static int v[] new int[1005];static int w[] new int[1005];public static void main(String[] args) {Scanner sca new Scanner(System.in);n sca.nextInt();m sca.nextInt();for (int i 1; i n; i) {v[i] sca.nextInt();w[i] sca.nextInt();}res dfs(1, m);System.out.println(res);}static int dfs(int x, int spV) {//x表示当前考虑第几个物品spV表示当前剩余的背包体积if (x n) return 0;//剩余背包体积不够放当前物品时只能不选考虑下一个物品if (spV v[x]) return dfs(x 1, spV);else if (spV v[x]) {//当背包剩余体积 当前物品体积时 有俩种选择 选/不选return Math.max(dfs(x 1, spV), dfs(x 1, spV - v[x]) w[x]);}return 0;}}题目代码 2——记忆化搜索模板 记忆化搜索 暴力dfs 记录答案 import java.util.Scanner;public class _01背包问题_dp2 {static int n, m, res 0;static int v[] new int[1005];static int w[] new int[1005];static int mem[][] new int[1005][1005];public static void main(String[] args) {Scanner sca new Scanner(System.in);n sca.nextInt();m sca.nextInt();for (int i 1; i n; i) {v[i] sca.nextInt();w[i] sca.nextInt();}res dfs(1, m);System.out.println(res);}static int dfs(int x, int spV) {//x表示当前考虑第几个物品spV表示当前剩余的背包体积if (mem[x][spV] ! 0) return mem[x][spV];int sum 0;if (x n) sum 0;//剩余背包体积不够放当前物品时只能不选考虑下一个物品else if (spV v[x]) sum dfs(x 1, spV);else if (spV v[x]) {//当背包剩余体积 当前物品体积时 有俩种选择 选/不选sum Math.max(dfs(x 1, spV), dfs(x 1, spV - v[x]) w[x]);}mem[x][spV] sum;return sum;}
}题目代码3——递推(dp) 递推的公式 dfs 向下递归的公式递推数组的初始值 递归的边界 import java.util.Scanner;public class _01背包问题_dp3 {static int n, m, res 0;static int v[] new int[1005];static int w[] new int[1005];static int dp[][] new int[1005][1005];public static void main(String[] args) {Scanner sca new Scanner(System.in);n sca.nextInt();m sca.nextInt();for (int i 1; i n; i) {v[i] sca.nextInt();w[i] sca.nextInt();}//从下往上推for (int i n; i 1; i--) {//i代表背包for (int j 0; j m; j) {//j代码背包体积if (j v[i]) {//如果背包不够装dp[i][j] dp[i 1][j];} else if (j v[i]) {dp[i][j] Math.max(dp[i 1][j], dp[i 1][j - v[i]] w[i]);}}}System.out.println(dp[1][m]);}
}
