admin管理员组

文章数量:1037775

记忆化搜索系列一＞猜数字大小II

题目分析：

这里是引用

暴搜设计：

这里是引用

改为记忆化搜索：

这里是引用

代码：

代码语言：javascript代码运行次数：0运行复制
class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n+1][n+1];
        return dfs(1,n);
    }

    private int dfs(int left, int rigth){
        
        if(left >= rigth) return 0;//递归出口，不存在(>)和不用花钱)(=)
        
        if(memo[left][rigth] != 0) return memo[left][rigth];

        int ret = 0x3f3f3f3f;
        for(int head = left; head <= rigth; head++){
            int x = dfs(left,head-1);//猜大了
            int y = dfs(head+1,rigth);//猜小了
            ret = Math.min(Math.max(x,y)+head, ret);
        }

        memo[left][rigth] = ret;
        return memo[left][rigth];
    }
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-14，如有侵权请联系 cloudcommunity@tencent 删除intreturn递归设计搜索

记忆化搜索系列一＞猜数字大小II

题目分析：

这里是引用

暴搜设计：

这里是引用

改为记忆化搜索：

这里是引用

代码：

代码语言：javascript代码运行次数：0运行复制
class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n+1][n+1];
        return dfs(1,n);
    }

    private int dfs(int left, int rigth){
        
        if(left >= rigth) return 0;//递归出口，不存在(>)和不用花钱)(=)
        
        if(memo[left][rigth] != 0) return memo[left][rigth];

        int ret = 0x3f3f3f3f;
        for(int head = left; head <= rigth; head++){
            int x = dfs(left,head-1);//猜大了
            int y = dfs(head+1,rigth);//猜小了
            ret = Math.min(Math.max(x,y)+head, ret);
        }

        memo[left][rigth] = ret;
        return memo[left][rigth];
    }
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-14，如有侵权请联系 cloudcommunity@tencent 删除intreturn递归设计搜索

本文标签： 记忆化搜索系列一＞猜数字大小II

版权声明：本文标题：记忆化搜索系列一＞猜数字大小II 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748277416a2278833.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。