地图类网站开发实战教程,北京公司模板网站好,wordpress post 属性,工业设计网站哪个最文章目录题目描述思路 代码DFS动态规划新系列#xff5e;用于区分开高频题和每日一题#xff5e; 题目描述
一眼二分#xff0c;但是实际上并不是这题让我想到社团的猜数字游戏…但是给钱是真过分了
思路 代码
DFS
自底向上进行递归。Math.max(…
文章目录题目描述思路 代码DFS动态规划新系列用于区分开高频题和每日一题 题目描述
一眼二分但是实际上并不是这题让我想到社团的猜数字游戏…但是给钱是真过分了
思路 代码
DFS
自底向上进行递归。Math.max()因为可能选左边也可能选右边选取最大的作为保证
class Solution {static int[][] cache new int[201][201]; // 200 是最大npublic int getMoneyAmount(int n) {return dfs(1, n);}int dfs(int l, int r) {if(l r) return 0; // 就一个不用猜if(cache[l][r] ! 0) return cache[l][r]; // 已算过剪枝int ans Integer.MAX_VALUE; // 维护当前区间的最小值// 遍历区间值每个都猜for(int x l; x r; x) {// 自底向上 dfs选取较大的一个毕竟要保证所以左右都可能int cur Math.max(dfs(l, x - 1), dfs(x 1, r)) x; ans Math.min(ans, cur); // 选取}// 维护 cachecache[l][r] ans;return ans;}
}动态规划
总体思路和 DFS 差不多注意顺序保证无后效性
class Solution {public int getMoneyAmount(int n) {int[][] dp new int[n 2][n 2]; // 前后边界1 1for(int i n; i 1; --i) {// [j, i] 范围内for(int j i; j n; j) {if(i j) dp[i][j] 0; // 就一个不用判了else {dp[i][j] Integer.MAX_VALUE; // 维护 dp[i][j] 的最小值。选取 [i][k - 1]、[k 1][j] 的最大值// 在 [i, j] 中选一个for(int k i; k j; k) {int cur Math.max(dp[i][k - 1], dp[k 1][j]) k;dp[i][j] Math.min(dp[i][j], cur);}}}}return dp[1][n];}
}
