1. Toy模板网首页
  2. > Toy博客

LeetCode——动态规划

9月前 作者：小鱼0135 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了LeetCode——动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划

一、一维数组：斐波那契数列

  1. 爬楼梯70简单

    dp定义： dp[i]表示爬到第i阶有多少种不同的方式

    状态转移方程： dp[i] = dp[i-1] + dp[i-1] （每次可以爬1或2个台阶）

    边界条件： dp[0] = 1; dp[1] = 1;（满足dp[2] = 2）

    返回值： dp[n]，即通过累积，dp[n]为爬到第n阶台阶的方式

    改进： 因为dp只使用了前两个值，所以使用两个变量存储两个值，不断迭代更新。——试过之后与原dp数组相比改进不大，可能是因为题中n的值比较小，如果n的值较大的话，会节省空间开销。

  2. 打家劫舍198中等

    dp定义： dp[i]表示打劫到第i间房屋能偷窃到的最高金额

    状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + 第i间房屋的金额)

    边界条件： dp[0] = 0; dp[1] = nums[0]; (后续 要计算dp[i-2])

    返回值： dp[n]，即打劫到第n间房屋能偷窃到的最高金额

    改进： 同样可以缩小空间开销，在数组够长的时候可以进行节省。

  3. 打家劫舍Ⅱ213中等

    该题在上一题的基础上加了一个限制条件，房屋是环形，也就是在偷了第一间房的情况下不能偷最后一间；偷了最后一间的情况下不能偷第一间！！ 所以分为两种情况，从第1间到第n-1间，从第2间到第n间。

    dp定义： dp[i]表示打劫到第i间房屋能偷窃到的最高金额

    状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + 第i间房屋的金额)

    边界条件： 只有一间房屋，返回该房屋的金额；只有两间房屋，返回两间房屋中金额最大的；超过两间，根据特殊情况分别计算抢劫第1间房屋和最后一间房屋两种情况下能获取到的最高金额，将其返回。

    返回值： 盗窃金额最高的情况

    改进： 节省空间开销

总结：以上情况均使用了一维dp数组，且状态转移方程与数组的前几个数有关，可以使用变量存储，节省空间开销。关键对dp[i]的定义明确，状态转移方程确定好，在这种情况下再对边界情况进行特殊考虑。

二、二维数组：矩阵路径

  1. 矩阵的最小路径和64中等

    dp定义： dp[i][j]表示移动到[i][j]位置的时候路径上的数字和最小

    状态转移方程： dp[i][j] = min(dp[i-1][j] + [i][j]位置的数字, dp[i][j-1] + [i][j]位置的数字)

    边界条件： 第一行+[i][j-1], 第一列+[i-1][j]

    返回值： dp[m][n]

    题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12


    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int raw = grid.size();
        int col = grid[0].size();
        vector<vector<int>> dp(raw, vector<int>(col, 0));
        dp[0][0] = grid[0][0];
        for (int j = 1; j < col; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for (int i = 1; i < raw; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        // 遍历
        for (int i = 1; i < raw; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[raw-1][col-1];
    }
};

    改进： 空间优化，相当于对矩阵进行了压缩

    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int raw = grid.size();
        int col = grid[0].size();
        vector<int> dp(col);
        // 初始化
        dp[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            dp[i] = dp[i-1] + grid[0][i];
        }
        for (int i = 1; i < raw; i++) {
            dp[0] = dp[0] + grid[i][0];
            for (int j = 1; j < col; j++) {
                dp[j] = min(dp[j-1] + grid[i][j], dp[j] + grid[i][j]);
            }
        }
        return dp[col-1];
    }
};
  2. 不同路径62中等

    dp定义： dp[i][j]表示到[i][j]位置的路径总数

    状态转移方程： dp[i][j] = dp[i-1][j] + dp[i][j-1]

    边界条件： dp[0][j] = 1; dp[i][0] = 1

    返回值： dp[m-1][n-1]

    改进： 和上一题一样的思路

三、数组区间

  1. 数组区间和303简单

    dp定义： dp[i]表示从0-i的元素和

    状态转移方程： dp[i] = dp[i-1] + nums[i]

    边界条件： dp[0] = 0

    返回值： dp[right] - dp[left] + nums[left]

    改进： 这种情况下dp[right] - dp[left]之后包右不包左

  2. 数组中等差递增子区间的个数

    dp定义： dp[i]是i位置等差数列的个数，需要一个变量count记录到i位置之前等差数列的个数

    状态转移方程： 如果公差还为d，dp[i] = dp[i-1] + 1; 如果方差变化，d = nums[i] - nums[i-1]

    边界条件： d = nums[i] - nums[i-1], dp[0] = 0

    返回值： count

    改进： nums[i] - nums[i-1] = nums[i-1] - nums[i-2] 隐含了判断等差数列的长度大于等于3

    改进代码：

    class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        // 长度必须大于3，所以如果数列长度小于3，返回0
        if (n < 3) {
            return 0;
        }
        vector<int> dp(n);
        dp[0] = 0;
        dp[1] = 0;
        // 等差数列个数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
                count += dp[i];
            }
        }
        return count;
    }
};

四、分割整数

  1. 分割整数的最大乘积343

    dp定义： dp[i] 表示第i个数拆分后可以得到的最大乘积，会成为后面数的因数。

    状态转移方程： i表示当前要计算最大乘积的数，j表示i的某个因数

    for (int i = 2; i <= n; i++) {
	int curMax = 0;
    for (int j = 1; j < i; j++) {
        curMax = max(curMax, max(j* (i-j), j * dp[i-j]));
    }
	dp[i] = curMax;
}

    边界条件： 拆分的正整数的个数大于2，所以dp[0] = 0; dp[1] = 1

    返回值： dp[n]

    改进：文章来源地址https://www.toymoban.com/news/detail-776678.html

  2. 按平方数来分割整数279中等

    dp定义： dp[i]表示i的完全平方数的最小数量

    状态转移方程：

    for (int i = 1; i <= n; i++) {
	int minValue = INT_MAX;
    for (int j = 1; j * j <= i; j++) {
        minValue = min(minValue, dp[i-j*j]);
    }
    dp[i] = minValue + 1;
}

    边界条件： dp[0] = 0

    返回值： dp[n]

    改进：

  3. 分割整数构成字母字符串91中等

    dp定义： dp[i]表示0-i位置有的编码方式

    状态转移方程： 因为26个字母编码有两位数，而且前缀0是不能包含在两位数的，所以分为两种情况：

    第一种是只把加第i个数当成编码：

    if (s[i-1] != '0') {

	dp[i] += dp[i-1];

}

    第二种加上前一个数看是否构成新的编码：

    if (s[i-2] != 0 && ((s[i-2] - '0') * 10 + (s[i-1] - '0')) < 26) {
    dp[i] += dp[i-2];
}

    边界条件： dp[0] = 1;

    返回值： dp[n]

    改进：

五、最长递增子序列

  1. 最长递增子序列300中等

    dp定义： dp[i]表示从0-i可以构成递增子序列的最大长度

    状态转移方程： 因为可以删除数组中的某些元素，所以递增子序列要从之前的所有数检查。

    for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = i - 1; j>= 0; j--) {
        if (nums[j] < nums[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

    边界条件： dp[i] = 1，每个元素都是一个递增子序列

    返回值： dp数组中的最大值。

    改进： 贪心+二分查找

    贪心：因为我们想要上升子序列尽可能长，所以就要序列上升得尽可能慢，每次在上升子序列最后加上的数尽可能小

    dp定义：dp[i]表示长度为i的最长上升子序列的末尾元素的最小值，用len记录目前最长上升子序列的长度，起始为1

    状态转移方程：

    if (nums[i] > d[len]) {
    d[++len] = nums[i];
} else {
    // 二分查找
    int l = 1, r = len, pos = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (d[mid] < nums[i]) {
            pos = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    d[pos + 1] = nusm[i];-0
}

    边界条件：dp[1] = nums[0];

    返回值：len

  2. 一组整数对能够构成的最长链646中等

    dp定义： dp[i]表示以pairs[i]为结尾的最长数对链的长度

    状态转移方程： 先将数对链的第一个元素进行排序，以第i位为定点，遍历之前一共可以组成多少个数对链

    sort(pairs.begin(), pairs.end());
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (pairs[i][0] > pairs[j][1]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

    边界条件： 无

    返回值： dp[n-1]

    改进： 按元组的第二个数的大小进行排序

  3. 最长摆动子序列376中等

    dp定义： 两个dp分别定义上升序列up和下降序列down

    状态转移方程：

    如果差是正，up序列更新，如果差是负，down序列更新，如果差为0都不更新。

    up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
    if (nums[i] > nums[i-1]) {
        up[i] = max(up[i-1], down[i-1] + 1);
        down[i] = down[i-1];
    } else if (nums[i] < nums[i-1]) {
        down[i] = max(down[i-1], up[i-1] + 1);
        up[i] = up[i-1];
    } else {
        up[i] = up[i-1];
        down[i] = down[i-1];
    }
}

    边界条件： up[0] = down[0] = 1;

    返回值： max(down[i-1], up[i-1]);

    改进： 减少空间消耗，使用up和down两个变量进行存储

    int up = 1, dowm = 1
for (int i = 1; i < n; i++) {
    if (nums[i] - nums[i-1] > 0) {
        down += 1;
    } else if (nums[i] - nums[i-1] < 0){
        up += 1;
    }
}
return max(up, down);

六、最长公共子序列

  1. 最长公共子序列1143中等

    dp定义： dp[i][j]表示word1的第i位和word2的第j位之前序列的最长公共子序列

    状态转移方程：

    如果word1[i] == word2[j], dp[i][j] = dp[i-1][j-1] + 1

    如果word1[i] != word2[j], dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    边界条件： dp[0][0] = 0

    返回值： dp[n][m]

    改进：

七、0-1背包

  1. 划分数组为和相等的两部分416中等

    dp定义： dp[i][j]表示到nums数组的第i个位置，和能否是j，true表示和可以是j，false表示不可以

    状态转移方程：

    如果j < 当前数nums[i]，说明不能放入：dp[i][j] = dp[i-1][j]

    如果j > 当前数nums[i]，有两种情况：dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]

    边界条件：

    和为0，哪个元素都不选：dp[i][0] = true

    dp[0][nums[0]] = true

    返回值： dp[n-1][target]

    改进： 空间优化

  2. 改变一组数的正负号使得它们的和为一给定数494中等 —— 回溯递归

    应该想法简单一点，不能把全过程都想清楚，把子问题想明白就行

    dp定义：

    状态转移方程：

    边界条件：

    返回值：

    改进：

  3. 01字符构成最多的字符串474中等——三维数组

    dp定义： dp[i][j][k]三维dp数组，第一维表示在前多少个字符串中找0和1，j表示0的个数，k表示1的个数。

    状态转移方程：

    for (int i = 1; i <= length; i++) {
    // 计算该字符串中0和1的个数
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= n; k++) {
            dp[i][j][k] = dp[i-1][j][k];
            if (j >= zeros && k >= ones) {
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-zeros][k-ones] + 1);
            }
        }
    }
}

    边界条件： dp[0][j][k] = 0

    返回值： dp[length][m][n]

    改进：

  4. 找零钱的最少硬币数322中等

    dp定义： dp[i]表示金额和为i的最小硬币的数量

    状态转移方程：

    for (int i = 1; i <= amount; i++) {
    for (int j = 0; j < coins.size(); j++) {
        if (coins[j] <= i) {
            dp[i] = min(dp[i], dp[i-coins[j]] + 1);
        }
    }
}
if (dp[amount] > amount) {
    return -1;
}
return dp[amount];

    边界条件： dp[0] = 0；dp[other] = amount + 1(表示没有构成amount金额的方案);

    返回值： 如果硬币不能构成所需金额，则返回-1；如果硬币可以构成所需金额，返回所需的最小硬币数。

    改进：

  5. 找零钱的硬币数组合518中等

    dp定义： dp[i]表示和为i的总方案数

    状态转移方程：

    for (int i = 1; i <= amount; i++) {
    for (int j = 0; j < coins.size(); j++) {
        if (i >= coins[j]) {
            dp[i] += dp[i-coins[j]] + 1;
        }
    }
}
return dp[amount];

    边界条件： dp[0] = 0

    返回值： dp[amount]

    改进：

  6. 字符串按单词列表分割139中等

    dp定义： dp[i]表示截止i位置前的字符串是否可以有wordDict中的单词构成

    将wordDict进行去重是因为可以减小重复计算

    状态转移方程：

    vector<bool> dp(s.size() + 1);
for (int i = 1; i <= size(); i++) {
    for (int j = 0; j < i; j++) {
        if (dp[j] && wordDictSet.find(s.substr(j, i - 1)) != wordDictSet.end()) {
            dp[i] = true;
            break;
        }
    }
}

    边界条件： dp[0] = true

    返回值： dp[s.size()]

    改进：

  7. 组合总和377组合总和Ⅳ

    dp定义： dp[i] 表示和为i时的元素组合个数

    状态转移方程：

    for(int i = 1; i <= target; i++) {
    for (int j = 0; j < nums.size(); j++) {
        if (i >= nums[j] && dp[i - nums[j]] < INT_MAX - dp[i]) {
            dp[i] += dp[i - nums[j]];
        }
    }
}

    边界条件： dp[0] = 1

    返回值： dp[target]

    改进：

八、股票交易

允许的交易次数

​ 能否在同一天进行买卖

​ 增加限制条件要增加维度

  1. 股票交易Ⅰ 121简单

    dp定义： 最简单的情况，只有一个限制是不能在同一天进行买卖，只进行一次交易，dp[i]表示第i天卖出能获得的最大利润

    状态转移方程：

    dp[i] = max(dp[i-1], prices[i] + minprices)

    边界条件：

    dp[0] = 0;

    返回值： dp[n]

    改进： 空间优化，两个变量buy和sell分别保存

    int buy = -prices[0];
int sell = 0;
for (int i = 1; i < n; i++) {
    buy = max(buy, -prices[i]);
    sell = max(sell, buy + prices[i]);
}
  2. 股票交易Ⅱ 122中等

    没有限制交易次数

    可以在同一天进行买卖

    dp定义： dp[i][j]表示第i天的买入（j=0）可以获得的最大利润和第i天卖出（j=1）可以获得的最大利润

    状态转移方程：

    dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);

    dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);

    边界条件：

    dp[0][0] = -prices[0];

    dp[0][1] = 0;

    返回值： dp[n-1][1]

    改进： 空间优化

    int buy = -prices[0];
int sell = 0;
for (int i = 1; i < n; i++) {
    // int temp_buy = max(buy, sell - prices[i]);
    // int temp_sell = max(sell, buy + prices[i]);
    // buy = temp_buy;
    // sell = temp_sell;
    // 第二种
    // int temp_buy = buy;
    // int temp_sell = sell;
    // buy = max(temp_buy, temp_sell - prices[i]);
    // sell = max(temp_sell, temp_buy + prices[i]);
    // 第三种
    buy = max(buy, sell - prices[i]);
    sell = max(sell, buy + prices[i]);
}
return sell;
  3. 股票交易Ⅲ123困难

    两次交易

    允许同一天买卖

    dp定义： dp[i][j]表示第i天的利润，j=0表示第一次买入；j=1表示第一次卖出；j=2表示第二次买入；j=3表示第二次卖出

    状态转移方程：

    dp[i][0] = max(dp[i-1][0], -prices[i]);

    dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);

    dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);

    dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);

    边界条件：

    dp[0][0] = -prices[0];

    dp[0][2] = -prices[0];

    返回值： dp[n-1][3]

    改进： 空间优化

    for (int i = 1; i < n; i++) {
    // 第一种
    // int temp_buy1 = buy1;
    // int temp_sell1 = sell1;
    // int temp_buy2 = buy2;
    // int temp_sell2 = sell2;
    // buy1 = max(temp_buy1, -prices[i]);
    // sell1 = max(temp_sell1, temp_buy1 + prices[i]);
    // buy2 = max(temp_buy2, temp_sell1 - prices[i]);
    // sell2 = max(temp_sell2, temp_buy2 + prices[i]);

    // 第二种
    buy1 = max(buy1, -prices[i]);
    sell1 = max(sell1, buy1 + prices[i]);
    buy2 = max(buy2, sell1 - prices[i]);
    sell2 = max(sell2, buy2 + prices[i]);
}
  4. 股票交易Ⅳ188困难

    K次交易

    允许同一天进行买卖

    dp定义： 定义dp数组，i表示第i天，k表示完成了k次交易，j有两个状态，1表示手中持有股票，0表示手中没有股票

    状态转移方程：

    // 状态转移
for (int i = 1; i < n; i++) {
    for (int K = 1; K <= k; K++) {
        dp[i][K][0] = max(dp[i-1][K][0], dp[i-1][K-1][1] + prices[i]);
         dp[i][K][1] = max(dp[i-1][K][1], dp[i-1][K][0] - prices[i]);
    }
}

    边界条件：

    // 初始化
for (int i = 0; i <= k; i++) {
    dp[0][i][0] = 0;
	dp[0][i][1] = -prices[0];
}
for (int i = 1; i < n; i++) {
	dp[i][0][0] = 0;
	dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][0] - prices[i]);
}

    返回值： dp[n-1][k][0]

    改进：

  5. 需要冷却期的股票交易309中等

    没有限制交易次数

    允许同一天进行买卖，但是卖掉之后要有一天冷冻期，在冷冻期内不能买入股票

    dp定义： dp[i][j], j的范围是0, 1, 2，分别表示i位置买入，卖出、冷冻的最大利润

    状态转移方程：

    dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])

    dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

    dp[i][2] = max(dp[i-1][2], dp[i-1][1])

    边界条件： dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0;

    返回值： max(dp[n][0], max(dp[n][1], dp[n][2]));

    改进： 空间优化，因为只用到了i-1时候的利润，所以可以减小一个维度，用三个变量来存储上一次买入、卖出、冷冻的最大利润

    int n = prices.size();
// 初始化
int get = -prices[0];
int out = 0;
int no = 0;
for (int i = 1; i < n; i++) {
    // 第一种
    // int temp_get = get;
    // int temp_out = out;
    // int temp_no = no;
    // get = max(temp_get, temp_no - prices[0]);
    // out = max(temp_out, temp_get + prices[0]);
    // no = max(temp_no, temp_out);
    
    // 第二种，冷冻期只有上一天卖出之后的后一天为冷冻期
    int temp_out = out;
    get = max(get, no - prices[i]);
    out = get + prices[i];
    no = max(temp_out, no);
}
  6. 需要交易费用的股票交易714中等

    dp定义： dp[i][j]表示到第i支股票时，j=0时表示买入的利润，j=1时表示卖出的利润

    状态转移方程：

    dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i] - fee)

    dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

    边界条件： dp[0][0] = -prices[i] - fee

    返回值： dp[n][1]

    改进： 空间优化，因为只用到了前一天的买入、卖出的值，所以只需要两个变量进行存储

    int get = -prices[0] - fee;
int out = 0;
for (int i = 1; i < n; i++) {
    // 第一种
    // int temp_get = get;
    // int temp_out = out;
    // get = max(temp_get, temp_out - prices[i] - fee);
    // out = max(temp_out, temp_get + prices[i]);
    
    // 第二种
    get = max(get, out - prices[i] - fee);
    out = max(get + prices[i], out);
}

九、字符串编辑

1. 删除两个字符串的字符使他们相等583

本质：二维DP

dp定义： dp[i][j]表示word1的i位置和word2的j位置最长公共子序列的长度，删除操作数为两个字符串的长度和减去两倍最长公共子序列的长度

状态转移方程：

if (word1[i-1] == word2[j-1]) {
    dp[i][j] = dp[i-1][j-1] + 1;
} else {
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

边界条件： dp[0][j] = 0; dp[i][0] = 0;

返回值： (n + m) - 2 * dp[n][m]

改进：

2. 编辑距离72困难

dp定义： dp[i][j]表示word1的第i个位置与word2的第j个位置相同的话需要的最少操作数，行表示插入，列表示删除，对角线表示

状态转移方程：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (word1[i-1] = word2[j-1]) {
            dp[i][j] = dp[i-1][j-1];
        } else {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
        }
    }
}

边界条件： dp[i][0] = i，表示删除；dp[0][j] = j，表示插入。

返回值： dp[n][m]

改进：

3. 复制粘贴字符650中等

dp定义： dp[i]表示能够打印i个’A’的最少操作次数

状态转移方程：

for (int i = 2; i <= n; i++) {
    dp[i] = INT_MAX;
    for (int j = 1; j * j <= i; j++) {
        if (i % j == 0) {
            dp[i] = min(dp[i], min(dp[i / j] + j, dp[j] + i / j));
        }
    }
}

边界条件： dp[1] = 0

返回值： dp[n]

改进：

主要是思想的一些记录~

到了这里，关于LeetCode——动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • LeetCode算法题解（动态规划）|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    LeetCode算法题解（动态规划）|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接：343. 整数拆分 题目描述： 给定一个正整数  n  ，将其拆分为  k  个  正整数  的和（  k = 2  ），并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析： 定义dp数组及下标含义： dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(39)
  • 算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    题目链接🔥🔥 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于

    2024年02月10日
    浏览(39)

  • 前端算法题——给定一个整数数组，判断是否存在重复元素。

    题目可以理解为如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false。 这题一看就是 计数问题，题目中“如果存在一值在数组中出现至少两次”这句话就告诉我们记录每一个数字出现的次数就能解决问题了。  我们遍历数组时，

    2024年02月20日
    浏览(80)
  • 【LeetCode题目详解】第九章 动态规划part03 343. 整数拆分 96.不同的二叉搜索树 （day41补）

    【LeetCode题目详解】第九章 动态规划part03 343. 整数拆分 96.不同的二叉搜索树 （day41补）

    给定一个正整数  n  ，将其拆分为 k 个 正整数 的和（  k = 2  ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 看到这道题目，都会想拆成两个呢，还是三个呢，还是四个.... 我们来看一下如何使用动规来解决。 # 动态规划 动

    2024年02月10日
    浏览(43)
  • 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。（哈希法）

    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。（哈希法）

    思路： 当题意中需要判断某个元素是否出现过，或者某个元素是否在这个集合里出现过。 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组

    2024年02月08日
    浏览(53)

  • 3的幂，给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false。

    题记： 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x 示例 1： 输入 ：n = 27 输出 ：true 示例 2： 输入 ：n = 0 输出 ：false 示例 3： 输入 ：n = 9 输出 ：true 示例 4： 输入 ：

    2024年02月15日
    浏览(51)

  • 给定一个非负整数a,返回＞=a，并且离a最近的，2的某次方(java)

    给定一个非负整数num，如何不用循环语句，返回=num，并且离num最近的，2的某次方 题目交代不能用循环,我们可以用位运算解决这题. 举个例子. 7 的 二进制是 0000 0111 第一步 先减一,n = 0000 0110 第二步,上面减一得到的结果n 或上n 右移一位. n |= n 1; 第三步.n 在 或 n 右移2位. n |=

    2024年02月09日
    浏览(44)
  • 343. 整数拆分(动态规划)

    343. 整数拆分(动态规划)

    给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k = 2 ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 本题比之前面的动态规划

    2024年01月20日
    浏览(48)

  • 【力扣】343. 整数拆分 ＜动态规划、数学＞

    给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k = 2 ），并使这些整数的乘积最大化。返回可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 动态规划 确定 dp 数组以及下

    2024年02月09日
    浏览(42)
  • 整数拆分（力扣）动态规划 JAVA

    整数拆分（力扣）动态规划 JAVA

    给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k = 2 ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 里程碑意义 解题思路：

    2024年02月17日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包