首页 > 代码库 > 好,开始没做出来 guess-number-higher-or-lower-ii
好,开始没做出来 guess-number-higher-or-lower-ii
https://leetcode.com/mockinterview/session/result/xsicjnm/
https://leetcode.com/problems/guess-number-higher-or-lower-ii/
// https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation // https://en.wikipedia.org/wiki/Minimax // 开始我的思路有问题,我是先选择区间,最后收敛到结果数 // 实际上work的思路是,先选择数字,再走向某个区间,然后取两个区间中的更大值 class Solution { int ** table; int DP(int s, int e) { if (s >= e) { return 0; } if (table[s][e] != INT_MAX) { return table[s][e]; } int local_max = INT_MAX; for (int k=s; k<=e; ++k) { // 下面这个表达式很重要 local_max = min(k + max(DP(s, k-1), DP(k+1, e)), local_max); } table[s][e] = local_max; return local_max; } public: int getMoneyAmount(int n) { table = new int*[n+1]; for (int i=0; i<n+1; ++i) { table[i] = new int[n+1]; for (int j=0; j<n+1; ++j) { table[i][j] = INT_MAX; } } int ret = DP(1, n); for (int i=0; i<n+1; ++i) { delete[] table[i]; } delete[] table; return ret; } }; // 用Java又做了一遍 package com.company; import java.util.ArrayList; import java.util.List; class Solution { int[][] dp; int get(int s, int e) { if (s >= e) { // 注意,只有一个的话,不用猜 return 0; } if (dp[s][e] != 0) { return dp[s][e]; } // 注意Java的是这种形式的MIN/MAX int min = Integer.MAX_VALUE; for (int i=s; i<=e; i++) { int tmp = Math.max(get(s, i-1), get(i+1, e)) + i; if (tmp < min) { min = tmp; } } dp[s][e] = min; return min; } public int getMoneyAmount(int n) { // 看了之前做的内容,思路还是很清晰的 // 要用DP的时候,不要犹豫 dp =new int[n+1][n+1]; int ret = get(1, n); return ret; } } public class Main { public static void main(String[] args) { // write your code here System.out.println("Hello"); Solution solution = new Solution(); int ret = solution.getMoneyAmount(3); System.out.printf("Get ret: %d\n", ret); } }
好,开始没做出来 guess-number-higher-or-lower-ii
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。