美文网首页
(区间dp,minmax问题,极大极小)375. 猜数字大小 I

(区间dp,minmax问题,极大极小)375. 猜数字大小 I

作者: 来到了没有知识的荒原 | 来源:发表于2021-08-04 08:30 被阅读0次

375. 猜数字大小 II

class Solution {
public:
    int getMoneyAmount(int n) {
        int dp[n + 2][n + 2];
        memset(dp, 0, sizeof dp);
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = 1e9;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j]));
                }
            }
        }
        return dp[1][n];
    }
};

相关文章

  • (区间dp,minmax问题,极大极小)375. 猜数字大小 I

    375. 猜数字大小 II[https://leetcode-cn.com/problems/guess-numb...

  • MinMax-极小极大算法——2048

    Github上找到的是JS的代码,个人用Python重写了,代码之后会开源在github上。 算法介绍 MinMa...

  • 特征标准化作用

    1、minmax normalization(最值归一) 该方法会被极大极小离群值影响 from sklearn....

  • lintcode 476. 石子归并

    经典区间dp问题 链接 这道题里dp[i][j] 代表归并i 到j 所需要的最小成本, 对于k, 有j> k >=...

  • 区间类DP总结

    区间类DP的做法,是用memorized search,把大区间拆分为小区间来解。而dp[i][j] 则直观的表示...

  • LeetCode之Unique Paths(Kotlin)

    问题: 方法:经典的动态规划问题,dp[i][j] = dp[i-1][j] + dp[i][j-1],然后dp遍...

  • 区间DP和回文为主题的DP

    区间DP 区间DP的特征: 可以两个或多个部分进行整合, 或者反过来;能将问题分解为能两两合并的形式.区间DP的求...

  • 416. 分割等和子集

    一 题目: 二 思路: 背包问题 状态定义:dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数...

  • 极小,极大

    我们每人都是这个世界上渺小微茫的存在。 该不该亲近这个世界,该不该善待这个世界。 该不该抽离这个世界,该不该诋毁这...

  • CodeVS 2598 编辑距离问题 题解

    首先分析该问题,看数据大小,应当是一道dp题目,本题求得是最小值 状态分析 dp[i][j]表示,字符串A前i个字...

网友评论

      本文标题:(区间dp,minmax问题,极大极小)375. 猜数字大小 I

      本文链接:https://www.haomeiwen.com/subject/wjadvltx.html