375. Guess Number Higher or Lower II

cloud 发布于2019-08-14 17:28 / 3291人阅读

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

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];
    }
}

云服务器 GPU云服务器 Higher Guess Lower lower_case_table_nam

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

转载请注明本文地址：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 2019-08-19 11:34 评论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 2019-08-14 18:01 评论0 收藏0
前端 | 每天一个 LeetCode

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

张汉庆 2019-08-23 13:42 评论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 2019-07-25 10:20 评论0 收藏0