375. Guess Number Higher or Lower II

cloud 發布于2019-08-14 17:28 / 3306人閱讀

摘要：題目鏈接又是一道的題，關鍵是找。表示最少的，當范圍是的時候。所以要求就應該遍歷切分點找出最小的值，這個切分點可能把問題分成左邊或者右邊，要取最大值才能保證所有的值都能贏。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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