刷题日志【4】

1、猜数字大小

题意有点抽象，我大概讲一下，就是在1——n里面会有一个目标数，我们通过猜数字的方式逼近这个数字，直到解出这个数，之前我们是用二分法求最快达到求解的问题，这道题多了每次猜错都要付钱，不要求最快达到，只要求，不论题目的目标数是1——n里的哪一个，你口袋的钱在面对1——n的目标数时，都有解。

再简单点说，当n=5时，即总数字（1 2 3 4 5），不论目标数（x）是哪一个，你的钱都够逼出目标数，注意：这里不是指你的钱够面对目标数（x）的最差情况（如先猜：1 2 3······x，虽然这不一定是代价最高的，但估计不是最优的猜数字策略），而是钱够应对目标数为x的最佳情况（下面有举例解释）

1——10的最优策略如上，可以看到即使目标数是叶子节点（2，3 ，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->【1，0】->无意义return 0【1 0】理论情况不可能出现，不用代价
        //头节点：2->【1 1】return 0-->直接猜到了，所以【1 1】不用耗费代价
if(i>=j){return 0;}
int ret=INT_MAX;
for(int head=i;head<=j;head++)
{
int x=dfs(i,head-1);
int y=dfs(head+1,j);
//取两者较大值，满足最大值即该策略全部数字都可以达到
int cost=max(x,y)+head;
//遍历每一种不同的头节点，每一个max都是对应的头节点可以实现全部数字的代价
//我们要的是全部可行代价里最小的
ret=min(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->【1，0】->无意义return 0【1 0】理论情况不可能出现，不用代价
        //头节点：2->【1 1】return 0-->直接猜到了，所以【1 1】不用耗费代价
if(i>=j){return 0;}
if(memo[i][j]!=0){return memo[i][j];}
int ret=INT_MAX;
for(int head=i;head<=j;head++)
{
int x=dfs(i,head-1);
int y=dfs(head+1,j);
//取两者较大值，满足最大值即该策略全部数字都可以达到
int cost=max(x,y)+head;
//遍历每一种不同的头节点，每一个max都是对应的头节点可以实现全部数字的代价
//我们要的是全部可行代价里最小的
ret=min(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(vector<vector<int>>& matrix) {
        m=matrix.size();
        n=matrix[0].size();
    
       int maxlength=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                check[i][j]=true;
                //dfs返回以【i ,j】为头节点的最长路径
              maxlength=max(maxlength,dfs(matrix,i,j));  
                check[i][j]=false;
            }
        }


return maxlength;
    }

    int dfs(vector<vector<int>>& matrix,int i,int j) 
    {
        //!=0即意味着这个位置之前记录过
if(memo[i][j]!=0)
{
    return memo[i][j];
}
int tmp=0;
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];

if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&matrix[x][y]>matrix[i][j])
{check[x][y]=true;
tmp=max(tmp,dfs(matrix,x,y));
check[x][y]=false;


}

}
memo[i][j]=1+tmp;
return memo[i][j];


    }
};