资讯专栏INFORMATION COLUMN

375. Guess Number Higher or Lower II

cloud / 3305人阅读

摘要:题目链接又是一道的题,关键是找。表示最少的,当范围是的时候。所以要求就应该遍历切分点找出最小的值,这个切分点可能把问题分成左边或者右边,要取最大值才能保证所有的值都能赢。

375. Guess Number Higher or Lower II

题目链接:https://leetcode.com/problems...

又是一道dp的题,关键是找subproblem。dp[i][j]表示最少的money you need to guarantee a win,当范围是(i+1, j+1)的时候。所以要求dp[i][j]就应该遍历切分点找出最小的值,这个切分点可能把问题分成左边或者右边,要取最大值才能保证所有的值都能赢。所以
dp[i][j] = min(k+1 + max(dp[i][k-1], dp[k+1][j]))
注意base case:dp[i][i] = 0, dp[i][i+1] = i + 1

public class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n][n];
        for(int i = 0; i < n - 1; i++) dp[i][i+1] = i + 1;
        
        for(int len = 2; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                int j = i + len;
                for(int k = i + 1; k < j; k++) {
                    int cur = k + 1 + Math.max(dp[i][k-1], dp[k+1][j]);
                    if(dp[i][j] == 0 || dp[i][j] > cur) dp[i][j] = cur;
                }
            }
        }
        return dp[0][n-1];
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66653.html

相关文章

  • leetcode375. Guess Number Higher or Lower II

    摘要:猜对则本次猜测免费,猜错则本次猜测需要花费和数字等额的金钱。其实这题的英文表述有些问题,确切来说,在所有能够确保找到目标值的方法中,找到花费金钱最少的哪种。当等于时,即从中找到目标数字,确保找到一个数字至少需要多少钱。 题目要求 We are playing the Guess Game. The game is as follows: I pick a number from 1 ...

    focusj 评论0 收藏0
  • Leetcode 相似题只有题号不含代码。

    找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

    StonePanda 评论0 收藏0
  • 前端 | 每天一个 LeetCode

    摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...

    张汉庆 评论0 收藏0
  • python learn 01 basic

    摘要:输入的模块上使用。我们看到它包含一个庞大的属性列表。默认地,它返回当前模块的属性列表。 Python Learn Part More_Info Content List 1.Python Introduce 1.1 python REPL 1.2 python helloworld.py 1.3 python help() 1.4 to python_string 1.5 dif...

    MageekChiu 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<