网站建设建网站做网站网站设计,网页区设计网站诊断,网站平台开发与应用面试,重庆建网站价格文章目录 [2312. 卖木头块](https://leetcode.cn/problems/selling-pieces-of-wood/)思路1:用DFS进行记忆化搜索代码#xff1a;思路2:动态规划代码#xff1a; 2312. 卖木头块 思路1:用DFS进行记忆化搜索
1.要用DFS深度优先遍历每一种情况。在递归的同时#xff0c;不断更… 文章目录 [2312. 卖木头块](https://leetcode.cn/problems/selling-pieces-of-wood/)思路1:用DFS进行记忆化搜索代码思路2:动态规划代码 2312. 卖木头块 思路1:用DFS进行记忆化搜索
1.要用DFS深度优先遍历每一种情况。在递归的同时不断更新得到的最大值作为该方案的答案。保存在f中
2.因为在深度优先遍历的时候会重复所以递归的结束的条件为f有记录返回该几率。如果为空进行答案的计算
3.首先要根据给出的初始模板的宽和高确定存储价格的d数组和存储方法价格的f数组的大小
4.遍历prices数组将得到的价格存储到d中。
5.进行DFS记忆化搜索。不仅要跟新从高切割的各种可能性还要更新从款切割的可能性。
代码 private int[][] d;private Long[][] f;public long sellingWood(int m, int n, int[][] prices) {d new int[m 1][n 1];//d存的是对应的价格f new Long[m 1][n 1];//f存答案//设置二维数组的大小for (int[] var : prices) {d[var[0]][var[1]] var[2];}//遍历price数组将每一块宽和高所对应的价格存进d中//return dfs(m, n);//进行深度优先遍历计算钱数}private long dfs(int h, int w) {if (f[h][w] ! null) {return f[h][w];}//如果高和宽已经被计算过了直接返回long ans d[h][w];for (int i 1; i h / 2 1; i) {ans Math.max(ans, dfs(i, w) dfs(h - i, w));}for (int i 1; i w / 2 1; i) {ans Math.max(ans, dfs(h, i) dfs(h, w - i));}return f[h][w] ans;}
思路2:动态规划
代码 public long sellingWood(int m, int n, int[][] prices) {int[][] d new int[m 1][n 1];long[][] f new long[m 1][n 1];for (int[] var : prices) {d[var[0]][var[1]] var[2];}for (int i 1; i m; i) {for (int j 1; j n; j) {f[i][j] d[i][j];for (int k 1; k i; k) {f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]);}for (int k 1; k j; k) {f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]);}}}return f[m][n];}点击移步博客主页欢迎光临~
