php网站调试环境搭建,软件开发方式,wordpress导航主题模板下载地址,wordpress网站案例目录
1、猜数字大小 1、猜数字大小 题意有点抽象#xff0c;我大概讲一下#xff0c;就是在1——n里面会有一个目标数#xff0c;我们通过猜数字的方式逼近这个数字#xff0c;直到解出这个数#xff0c;之前我们是用二分法求最快达到求解的问题#xff0c;这道题多了每…目录
1、猜数字大小 1、猜数字大小 题意有点抽象我大概讲一下就是在1——n里面会有一个目标数我们通过猜数字的方式逼近这个数字直到解出这个数之前我们是用二分法求最快达到求解的问题这道题多了每次猜错都要付钱不要求最快达到只要求不论题目的目标数是1——n里的哪一个你口袋的钱在面对1——n的目标数时都有解。 再简单点说当n5时即总数字1 2 3 4 5不论目标数x是哪一个你的钱都够逼出目标数注意这里不是指你的钱够面对目标数x的最差情况如先猜1 2 3······x虽然这不一定是代价最高的但估计不是最优的猜数字策略而是钱够应对目标数为x的最佳情况下面有举例解释 1——10的最优策略如上可以看到即使目标数是叶子节点23 6 8 10沿着各个支路进行代价累计发现最大的也只是7-9-10)这一路计算得到16叶子节点是已经逼出来的答案不算代价所以一旦目标数不是叶子节点那代价只会更小所以以7为头节点的上图的策略是面对【1 10】的最佳策略 这里其实就有一个隐藏关系对应的一个【】一定是有一个对应的的最优策略即 【i j】的区间左右相同时就会是一样的策略对应的代价也是相同这里就是我们可以记忆化的地方 1、无记忆化
class Solution {public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int i,int j){//边界条件头节点为1-【10】-无意义return 0【1 0】理论情况不可能出现不用代价//头节点2-【1 1】return 0--直接猜到了所以【1 1】不用耗费代价
if(ij){return 0;}
int retINT_MAX;
for(int headi;headj;head)
{
int xdfs(i,head-1);
int ydfs(head1,j);
//取两者较大值满足最大值即该策略全部数字都可以达到
int costmax(x,y)head;
//遍历每一种不同的头节点每一个max都是对应的头节点可以实现全部数字的代价
//我们要的是全部可行代价里最小的
retmin(ret,cost);
}return ret;}
};
2、记忆化 就比上面的多了memo【】【】对每一种下标的return进行记录 class Solution {int memo[201][201];public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int i,int j){//边界条件头节点为1-【10】-无意义return 0【1 0】理论情况不可能出现不用代价//头节点2-【1 1】return 0--直接猜到了所以【1 1】不用耗费代价
if(ij){return 0;}
if(memo[i][j]!0){return memo[i][j];}
int retINT_MAX;
for(int headi;headj;head)
{
int xdfs(i,head-1);
int ydfs(head1,j);
//取两者较大值满足最大值即该策略全部数字都可以达到
int costmax(x,y)head;
//遍历每一种不同的头节点每一个max都是对应的头节点可以实现全部数字的代价
//我们要的是全部可行代价里最小的
retmin(ret,cost);
}
memo[i][j]ret;//记录下来方便其他的遍历到【i j】区间
return ret;}
};
2、矩阵中最长递增路径 发现相同的下标对应的最长路径一定是一样的只要matrix【2】的最长路径已知matrix【3】规划的路径里只要有matrix【2】,那么matrix【3】经过matrix【2】的最长路径一定是matrix【2】1加上他本身 所以在这里可以记忆化 class Solution {
int dx[4]{0,0,1,-1};
int dy[4]{1,-1,0,0};
//防止走回头录
bool check[201][201];
//备忘录
int memo[201][201];int m,n;public:int longestIncreasingPath(vectorvectorint matrix) {mmatrix.size();nmatrix[0].size();int maxlength0;for(int i0;im;i){for(int j0;jn;j){check[i][j]true;//dfs返回以【i ,j】为头节点的最长路径maxlengthmax(maxlength,dfs(matrix,i,j)); check[i][j]false;}}return maxlength;}int dfs(vectorvectorint matrix,int i,int j) {//!0即意味着这个位置之前记录过
if(memo[i][j]!0)
{return memo[i][j];
}
int tmp0;
for(int p0;p4;p)
{
int xidx[p];
int yjdy[p];if(x0xmy0yn!check[x][y]matrix[x][y]matrix[i][j])
{check[x][y]true;
tmpmax(tmp,dfs(matrix,x,y));
check[x][y]false;}}
memo[i][j]1tmp;
return memo[i][j];}
};
