算法 - 动态规划 / 贪心算法

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

🍺 动态规划

🍻 股票问题

🥂 🌸 121. 买卖股票的最佳时机 [数组] [股票] (动态规划)

class Solution {
private:
    vector<vector<int>> dp;     // dp[i][j]: 第 i 天持有 j 只股票
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        dp = vector<vector<int>>(n, vector<int>(2));
        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        // 状态转移
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                // 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                // 第i天有股 = 第i-1天有股 / 第一次买入
                dp[i][1] = max(dp[i - 1][1], - prices[i]);
            }
        }
        return dp[n - 1][0];
    }
};

🥂 🌸 122. 买卖股票的最佳时机Ⅱ [数组] [股票] (动态规划)

class Solution {
private:
    vector<vector<int>> dp;     // dp[i][j]: 第 i 天持有 j 只股票的利润
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        dp = vector<vector<int>>(n, vector<int>(2));
        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        // 状态转移
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                // 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                // 第i天有股 = 第i-1天有股 / 第i-1天无股, 并买入
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][0];
    }
};

🥂 🌸 123. 买卖股票的最佳时机Ⅲ [数组] [股票] (动态规划)

class Solution {
private:
    vector<vector<vector<int>>> dp; // dp[i][k][j]: 第 i 天交易 k 次持有 j 股的收益
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int K = 2;                  // 可以交易的次数
        dp = vector<vector<vector<int>>>(n, vector<vector<int>>(K + 1, vector<int>(2)));
        // base case
        for (int k = 0; k <= K; ++k) {
            dp[0][k][0] = 0;
            dp[0][k][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]);
        }
        // 状态转移
        for (int i = 1; i < n; ++i) {
            for (int k = 1; k <= K; ++k) {
                // 今天完成k笔交易无股 = 昨天完成k笔交易无股啥也没干 / 昨天完成k-1笔有股且卖了只股票
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k - 1][1] + prices[i]);
                // 今天完成k笔交易有股 = 昨天完成k笔交易有股啥也没干 / 昨天完成k笔无股今天买了只股票
                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
            }
        }
        return dp[n - 1][K][0];
    }
};

🥂 🌸 188. 买卖股票的最佳时机Ⅳ [数组] [股票] (动态规划)

class Solution {
private:
    vector<vector<vector<int>>> dp; // dp[i][k][j]: 第 i 天交易 k 次持有 j 股的收益
public:
    int maxProfit(int K, vector<int>& prices) {
        int n = prices.size();
        dp = vector<vector<vector<int>>>(n, vector<vector<int>>(K + 1, vector<int>(2)));
        // base case
        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]);
        }
        // 状态转移
        for (int i = 1; i < n; ++i) {
            for (int k = 1; k <= K; ++k) {
                // 今天完成k笔交易无股 = 昨天完成k笔交易无股啥也没干 / 昨天完成k-1笔有股且卖了只股票
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k - 1][1] + prices[i]);
                // 今天完成k笔交易有股 = 昨天完成k笔交易有股啥也没干 / 昨天完成k笔无股今天买了只股票
                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
            }
        }
        return dp[n - 1][K][0];
    }
};

🥂 🌸 309. 买卖股票的最佳时机含冷冻期 [数组] [股票] (动态规划)

class Solution {
private:
    vector<vector<int>> dp;     // dp[i][j]: 第 i 天持有 j 只股票的利润
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        dp = vector<vector<int>>(n, vector<int>(2));
        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        if (n > 1) {
            dp[1][0] = max(dp[0][0], dp[0][1] + prices[1]);
            // 前一天有股票 / 今天刚买
            dp[1][1] = max(dp[0][1], -prices[1]);
        }
        // 状态转移
        for (int i = 2; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                // 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                // 第i天有股 = 第i-1天有股 / 第i-1天无股, 并买入
                dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
            }
        }
        return dp[n - 1][0];
    }
};

🥂 🌸 714. 买卖股票的最佳时机含手续费 [数组] [股票] (动态规划)

class Solution {
private:
    vector<vector<int>> dp;     // dp[i][j]: 第 i 天持有 j 只股票的利润
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        dp = vector<vector<int>>(n, vector<int>(2));
        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        // 状态转移
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                // 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出, 但需要手续费
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
                // 第i天有股 = 第i-1天有股 / 第i-1天无股, 并买入
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][0];
    }
};

🍻 打家劫舍

🥂 🌸 198. 打家劫舍 [数组] [打劫] (动态规划)

class Solution {
private:
    vector<int> dp;     // dp[i]: 抢到第 i 家的最大金额
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        dp = vector<int>(n, 0);
        // base case
        dp[0] = nums[0];
        if (n > 0) {
            dp[1] = max(dp[0], nums[1]);
        }
        // 状态转移
        for (int i = 2; i < n; ++i) {
            // 抢上一家, 还是不抢上一家
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
};

🥂 🌸 213. 打家劫舍Ⅱ [数组] [打劫] (动态规划)

class Solution {
private:
    vector<int> dp1, dp2;     // dp[i]: 抢到第 i 家的最大金额
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 终止条件
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        dp1 = vector<int>(n - 1, 0);
        dp2 = vector<int>(n - 1, 0);
        // base case
        dp1[0] = nums[0];
        dp1[1] = max(dp1[0], nums[1]);
        // base case
        dp2[0] = nums[1];
        dp2[1] = max(dp2[0], nums[2]);
        // 状态转移   [0 1 2 3 4] -> [0 1 2 3]
        for (int i = 2; i < n - 1; ++i) {
            // 抢上一家, 还是不抢上一家
            dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        // 状态转移   [0 1 2 3 4] -> [1 2 3 4]
        for (int i = 2; i < n - 1; ++i) {
            // 抢上一家, 还是不抢上一家
            dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
        }
        return max(dp1[n - 2], dp2[n - 2]);
    }
};

🥂 🌸 337. 打家劫舍III [数组] [打劫] (动态规划) (递归)

class Solution {
private:
    unordered_map<TreeNode*, int> dp; // 抢到每个节点时的最大金额
public:
    int rob(TreeNode* root) {
        return traverse(root);
    }

    int traverse(TreeNode* root) {
        if (root == nullptr) return 0;
        // 备忘录有记, 返回金额
        if (dp.count(root)) return dp[root];
        // 做选择, 抢
        int q1 = root->val;
        if (root->left != nullptr) {
            q1 += traverse(root->left->left) + traverse(root->left->right);
        }
        if (root->right != nullptr) {
            q1 += traverse(root->right->left) + traverse(root->right->right);
        }
        // 做选择, 不抢
        int q2 = 0;
        q2 += traverse(root->left) + traverse(root->right);
        // 更新 dp
        dp[root] = max(q1, q2);
        return dp[root];
    }
};

🍻 背包问题

🥂 🌸 322. 零钱兑换 [数组] [背包] (动态规划)

class Solution {
private:
    vector<vector<int>> dp;     // 前 i 硬币凑齐 j 需要的最少硬币数
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        int n = coins.size();
        dp = vector<vector<int>>(n + 1, vector<int>(amount + 1, INT_MAX - 1));
        // base case
        dp[0][0] = 0;
        // 状态转移
        for (int i = 1; i <= n; ++i) {
            int cur = coins[i - 1];
            for (int j = 0; j <= amount; ++j) {
                if (cur <= j) {
                    // 前 i-1 个硬币凑成 j / 前 i 个硬币凑成 j-cur
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - cur] + 1); 
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][amount] == INT_MAX - 1 ? -1 : dp[n][amount];
    }
};

🥂 🌸 416. 分隔等和子集 [数组] [背包] (动态规划)

// 容量为 n 的背包, 是否可以装满 sum/2 的物品
class Solution {
private:
    vector<vector<bool>> dp;    // dp[i][j]: 前 i 个数是否可以装满 j
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        dp = vector<vector<bool>>(n + 1, vector<bool>(target + 1, false));
        // BASE CASE
        for (int i = 0; i <= n; ++i) {
            dp[i][0] = true;
        }
        // 状态转移方程
    	for (int i = 1; i <= n; ++i) {
            int cur = nums[i - 1];
    		for (int j = 1; j <= target; ++j) {
    			if (cur == j) {                 // 只用第 i 个数就可以凑齐
                    dp[i][j] = true;
                } else if (cur > j) {   // 看前 i-1 个是否可以凑齐
                    dp[i][j] = dp[i - 1][j];
                } else if (cur < j) {   // 前 i-1 个数可以凑齐或凑到 j-nums[i]
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - cur];
                }            
    		}
    	}
    	return dp[n][target];
    }
};

🥂 🌸 474. 一和零 [字符数组] [背包] (动态规划)

// 给定两个个容量为 m, n 的 0 1 背包, 看能装下多少个包含 0 1 的字符串 
class Solution {
private:
    vector<vector<vector<int>>> dp; // dp[i][j][k] 代表前 i 个 str 中可以放 j 个 0 k 个 1 的字符串数
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        dp = vector<vector<vector<int>>>(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
        // BASE CASE
        // dp[0][...][...] = 0;
        // 状态转移方程, 状态: 选不选第 i 个字符串
        // 选, dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - c0][k - c1])
        // 不选, dp[i][j][k] = dp[i - 1][j][k]
        for (int i = 1; i <= len; ++i) {
            pair<int, int> getZO = count(strs[i - 1]);
            int zeros = getZO.first, ones = getZO.second;
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= n; ++k) {
                    if (zeros <= j && ones <= k) {
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[len][m][n];
    }
    pair<int, int> count(string& str) {
        int zeros = 0, ones = 0;
        for (auto ch : str) {
            if (ch == '0') {
                zeros++;
            } else {
                ones++;
            }
        }
        return make_pair(zeros, ones);
    }
};

🥂 🌸 494. 目标和 [数组] [背包] (动态规划)

// 给两个背包, 一个背包里装正数, 一个装负数, 让和为 target
// 那么等价于让正背包里刚好凑满 (all + target) / 2
class Solution {
private:
    vector<int> dp; // dp[i][j]: 从前 i 个数字中可以组合成 j 的方案个数
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // BASE CASE
        int n = nums.size();
        // 现在有两个背包, 一个装正数, 一个装负数
        int total = 0;
        for (int i = 0; i < n; ++i) {
            total += nums[i];
        }
        if (abs(target) > total) return 0;          // 目标太大了, 不可能凑到
        if ((total + target) % 2 == 1) return 0;    // pos 不为整数
        int pos = (total + target) / 2;    
        dp = vector<int>(pos + 1, 0);
        dp[0] = 1;
        // 状态转移方程
        // dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]] 算上最后一个数/ 不算最后一个数
        for (int i = 1; i <= n; ++i) {
            int cur = nums[i - 1];
            for (int j = pos; j >= 0; --j) {
                if (cur <= j) { // 可以选或不选
                    dp[j] = dp[j] + dp[j - cur];
                } 
            }
        }
        return dp[pos];
    }
};

🥂 🌸 518. 零钱兑换Ⅱ [数组] [背包] (动态规划)

// 给定一个容量为 amount 的背包, 和一堆硬币, 凑满的方法有多少种
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j] 前 i 个货币凑齐 j 的方案数 
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        dp = vector<vector<int>>(n + 1, vector<int>(amount + 1, 0));
        // BASE CASE
        dp[0][0] = 1;
        // 状态转移方程
        for (int i = 1; i <= n; ++i) {
            int coin = coins[i - 1];                            // 当前硬币, 选不选
            for (int j = 0; j <= amount; ++j) {
                if (coin <= j) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coin];  // 不重复使用 coin/ 重复使用 coin
                } else {
                    dp[i][j] = dp[i - 1][j];                    // 不重复使用 coin
                }
            }
        }
        return dp[n][amount];
    }
};

🥂 🌸 1049. 最后一块石头的重量 [数组] [背包] (动态规划)

// 分成两堆石头, 正的, 负的
// sum = heap1 + heap2, heap1 < heap2
// 求 heap1 - heap2 的最小值 -> heap2 的最大值, 且 heap2 <= sum / 2
// 给一个容量为 sum / 2 的背包, 看最多能装多少石头
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]:前 i 石头装进 target 容量背包的最大石头量
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();          // 石头总量
        int sum = 0;
        for (auto& stone : stones) {
            sum += stone;
        }
        dp = vector<vector<int>>(n + 1, vector<int>(sum / 2 + 1, 0));
        // BASE CASE
        // dp[0][...] = 0;
        // 状态转移方程
        // 如果第 i 块石头装不下 dp[i][j] = dp[i - 1][j]
        // 如果第 i 块石头装得下 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i] + nums[i]])
        for (int i = 1; i <= n; ++i) {
            int stone = stones[i - 1];
            for (int j = 0; j <= sum / 2; ++j) {
                if (stone <= j) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stone] + stone);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return sum - 2 * dp[n][sum / 2];
    }
};

🍻 编辑距离

🥂 🌸 72. 编辑距离 [字符串] [编辑距离] (动态规划)

// 定义 dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的编辑距离
class Solution {
private:
    vector<vector<int>> dp;     // dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的编辑距离
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        // base case
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        // 状态转移
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 插入 or 删除 or 替换
                    // 如已知 i 与 j-1 相同 -> 那么让 i 与 j 相同则需添加一个 s1[i+1] = s2[j], 操作次数 +1
                    dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

🥂 🌸 583. 两个字符串的删除操作 [字符串] [编辑距离] (动态规划)

// 定义: dp[i][j]: 使 s1[0...i] s2[0...j] 相同的最少删除次数
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 使 s1[0...i] s2[0...j] 相同的最少删除次数
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        // base case
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        // 状态转移方程
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 删除 i or 删除 j
                    // 如已知 s1[0...i-1] == s2[0...j], 那么让 s1[0...i] == s2[0...j] 需要删除 s1[i], 操作 +1
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

🥂 🌸 1312. 让字符串成为回文串的最少插入次数 [字符串] [编辑距离] [回文] (动态规划)

// 定义 dp[i][j]: 对 s[i][j] 插入多少字符可以变为回文串
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 对 s[i...j] 插入多少个字符可以变为回文串
public:
    int minInsertions(string s) {
        int n = s.size();
        dp = vector<vector<int>>(n, vector<int>(n, 0));
        // BASE CASE
        // for (int i = 0; i < n; ++i) dp[i][i] = 0;
        // 状态转移方程
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len -1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                	// 在 i 处插入 or 在 j 处插入
                	// 已知 s[i+1...j] 是回文, 让 s[i...j] 是回文需要插入一个字符, 操作 +1
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
};

🥂 🌸 712. 两个字符串的最小 ASCII 删除和 [字符串] [编辑和] (动态规划)

// 定义 dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的最小删除和
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的最小删除和
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        // base case
        for (int i = 1; i <= m; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1];
        for (int j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1];
        // 状态转移方程
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 删除 s1[i] or s2[j]
                    // 比如 s1[0...i-1] == s2[0...j], 那么删除 s1[i] 两者就相等了
                    // dp[i][j] -> dp[i-1][j] 会增加删除和
                    dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

🍻 子序列

🥂 5. 最长回文子串 [数组] [回文子串] (动态规划)

class Solution {
private:
    vector<vector<int>> dp;             // dp[i][j]: 字符串 s[i...j] 的最长回文子串长度
    int m_len = 1, start = 0, end = 0;  // 记录最长回文子串的长度, start, end 
public:
    string longestPalindrome(string s) {
        int n = s.size();
        dp = vector<vector<int>>(n, vector<int>(n, 0));
        // base case
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 2;
            }
            if (dp[i][i + 1] > m_len) {
                m_len = dp[i][i + 1];
                start = i;
                end = i + 1;
            }
        }
        // 状态转移
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                // 子串也是回文
                if (s[i] == s[j] && dp[i + 1][j - 1] > 0) {
                    dp[i][j] = dp[i +1][j - 1] + 2;
                    // 更新最大子串信息
                    if (dp[i][j] > m_len) {
                        m_len = dp[i][j];
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substr(start, end - start + 1);
    }
};

🥂 53. 最大子数组和 [数组] [子序列] (动态规划)

// 定义: 以 nums[i] 结尾的数的最大子数组和
class Solution {
private:
    vector<int> dp;     // 以 nums[i] 结尾的数的最大子数组和
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        dp = vector<int>(n, 0); // dp 初始化
        // BASE CASE
        dp[0] = nums[0];
        // 状态转移方程
        for (int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
        }
        int res = *max_element(dp.begin(), dp.end());
        return res;
    }
};

🥂 139. 单词拆分 [字符串] > [单词拆分] > (动态规划)

// [字符串] > [单词拆分] > (动态规划)
// dp[i]: s[0...i) 是否可以被拼出
// dp[i] = dp[j] && uset.count(s[j...i)) -> s[0...i) = s[0...j) + s[j...i)
class Solution {
private:
    vector<bool> dp;
    unordered_set<string> uset; // 存放可以用于拼接的字符串
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        dp = vector<bool>(n + 1, false);
        for (auto& word : wordDict) {
            uset.insert(word);
        }
        // base case
        dp[0] = true;
        // 状态转移
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                // 如果 s[0...j) 可以被拼出, 且 s[j...i) 存在该单词
                if (dp[j] && uset.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

🥂 🌸 300. 最长递增子序列 [数组] [子序列] (动态规划)

// 定义: 以 nums[i] 结尾的最长子序列
class Solution {
private:
    vector<int> dp;     // 以 nums[i] 结尾的最长子序列
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // base case
        dp = vector<int>(n, 1);     // 初始化备忘录
        // 状态转移方程
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            } 
        }
        // 从备忘录中获取最大子序列
        int res = *max_element(dp.begin(), dp.end());
        return res;
    }
};

🥂 🌸 516. 最长回文子序列 [字符串] [子序列] [回文] (动态规划)

// 定义 dp[i][j]: 字符串 s[i...j] 的最长回文子序列
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: s[i...j] 的最长回文子序列
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        dp = vector<vector<int>>(n, vector<int>(n, 0));
        // BASE CASE
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        // 状态转移方程
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                	// 分别对应 去掉 i 处元素 or 去点 j 处元素 的回文数
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

🥂 🌸 1143. 最长公共子序列 [字符串] [子序列] (动态规划)

// 定义 dp[i][j]: 代表 s1[0...i] 与 s2[0...j] 的最长公共子序列
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 代表 s1[0...i] 与 s2[0...j] 的最长公共子序列
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        // base case
        // dp[0][...] = 0, dp[...][0] = 0;
        // 状态转移方程
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
};

🍻 路径和

🥂 🌸 64. 最小路径和 [矩阵] [路径和] (动态规划)

// 定义 dp[i][j]: 到达 (i,j) 的最小路径和
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 到达 (i,j) 的最小路径和
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        dp = vector<vector<int>>(m, vector<int>(n, 0));
        // BASE CASE
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; ++j) dp[0][j] = dp[0][j - 1] + grid[0][j];
        // 状态转移方程
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

🍻 爬楼梯

🥂 70. 爬楼梯 [矩阵] [跳法] (动态规划)

class Solution {
private:
    vector<int> dp;         // dp[i]: 爬上第 i 层有多少种爬法
public:
    int climbStairs(int n) {
        dp = vector<int>(n + 1, 0);
        // base case
        dp[0] = 1, dp[1] = 1;
        // 状态转移
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

🥂 🌸 174. 地下城游戏 [矩阵] [路径和] (动态规划) (逆向)

// 定义 dp[i][j]: 从 (i,j) 到达终点 (m-1, n-1) 的最小生命值
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 从 (i,j) 到达终点 (m-1, n-1) 的最小生命值
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        dp = vector<vector<int>>(m, vector<int>(n, 0));
        // base case
        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
        // 最后一列
        for (int i = m - 2; i >= 0; --i) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        // 最后一行
        for (int i = n - 2; i >= 0; --i) {
            dp[m - 1][i] = max(1, dp[m - 1][i + 1] - dungeon[m - 1][i]);
        }
        // 状态转移方程
        for (int i = m - 2; i >= 0; --i) {
            for (int j = n - 2; j >= 0; --j) {
                // 选一个值较小的方向走
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

🥂 🌸 787. K 站中转内最便宜的航班 [图] [K步最短路径] (动态规划) (bellman ford)

// 定义 dp[i][j]: 走过 i 步后, 到达 j 的最小费用
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 走过 i 步后, 到达 j 的最短费用
    const int INF = 0x3f3f3f3f;
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // k 站 代表 k+1 条边
        dp = vector<vector<int>>(k + 2, vector<int>(n, INF));
        dp[0][src] = 0;     // 走 0 步到达出发点的费用为 0
        // 只走一步, 只走两步 ... 
        for (int i = 1; i <= k + 1; ++i) {
            for (auto& flight : flights) {
                // start, end 为一条边的两端
                int start = flight[0], end = flight[1], cost = flight[2];
                dp[i][end] = min(dp[i][end], dp[i - 1][start] + cost);
            }
        }
        int res = INF;
        // 经过一/2/3/...步到达终点的最小值
        for (int i = 1; i <= k + 1; ++i) {
            res = min(res, dp[i][dst]);
        }
        // 如果走 i 步根本到不了终点
        return res == INF ? -1 : res;
    }
};

🥂 🌸 931. 下降路径最小和 [矩阵] [路径和] (动态规划) (扩展边界)

// 定义 dp[i][j]: 到达 (i,j) 的最小路径和
class Solution {
private:
    vector<vector<int>> dp;     // dp[i][j]: 到达 (i,j) 的最小路径和
    vector<vector<int>> dirts = {{-1, -1}, {-1, 0}, {-1, 1}};   // 方向
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        dp = vector<vector<int>>(m, vector<int>(n + 2, INT_MAX));
        // base case 
        for (int j = 1; j <= n; ++j) dp[0][j] = matrix[0][j - 1];
        // 状态转移方程
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (auto& dirt : dirts) {
                    // 左下, 正下, 右下
                    dp[i][j] = min(dp[i][j], dp[i + dirt[0]][j + dirt[1]]);
                }
                dp[i][j] += matrix[i][j - 1];
            }
        }
        int res = *min_element(dp[m - 1].begin(), dp[m - 1].end());
        return res;
    }
};

🍻 其他

🥂 140. 单词拆分Ⅱ [字符串] (动态规划) (递归)

class Solution {
private:
    unordered_set<string> uset;     // 存放待对比的字符串
    vector<vector<string>> dp;      // 备忘录, 记录 s[i...] 可以拼的句子有哪几种
    int n;                          // 字符串长度
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n = s.size(); this->n = n;                      // 字符串的长度
        dp = vector<vector<string>>(n, vector<string>(0));  // dp 初始化
        for (auto& word : wordDict) {                       // uset 初始化
            uset.insert(word);
        }
        vector<int> res = traverse(s, 0);                               // 调用递归函数
        return res;
    }
    // 获取 s[i...] 可以拼接的句子有哪些
    vector<string> traverse(string s, int i) {
        vector<string> cur_res;                             // 创建一个空的数组, 记录可行的字符串 
        // BASE CASE
        if (i == n) {                                       // 此时 s 字符串结束
            cur_res.push_back("");
            return cur_res;
        }
        // 获取备忘录, s[i...] 可以拼接的句子
        if (!dp[i].empty()) {
            return dp[i];
        }
        // 状态转移方程
        for (int len = 1; len + i <= n; ++len) {
            string subStr = s.substr(i, len);                   // 获取一个子单词
            if (uset.count(subStr)) {                           // 这个子单词可以被拼接
                vector<string> subFind = traverse(s, i + len);  // 子任务可以拼接的字符串有哪些
                for (auto& sub : subFind) {
                    if (sub.empty()) {                          // 防止最后一个单词后多个空格
                        cur_res.push_back(subStr);
                    } else {
                        cur_res.push_back(subStr + " " + sub);
                    }
                }
            }
        }
        // 更新备忘录
        dp[i] = cur_res;
        return cur_res;
    }
};

🥂 514. 自由之路 [字符串] [操作次数] (动态规划)

// 定义 dp[i][j]: 当前匹配 key[0...i], 从 ring[j] 开始移动需要操作多少次 
class Solution {
private:
    vector<vector<int>> dp; // dp[i][j]: 当前匹配 key[0...i], 从 ring[j] 开始移动需要操作多少次 
    unordered_map<char, vector<int>> umap;  // 字符对应的索引
public:
    int findRotateSteps(string ring, string key) {
        int m = key.size(), n = ring.size();
        dp = vector<vector<int>>(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; ++i) {
            umap[ring[i]].push_back(i);
        }
        // base case  key[0][0] 需要的操作部数
        for (auto& pos : umap[key[0]]) {
            dp[0][pos] = min(dp[0][pos], cal(n, 0, pos) + 1);
        }
        // 状态转移
        for (int i = 1; i < m; ++i) {       // 先选取 key 中的一个字符
            for (auto& pos : umap[key[i]]) {
                // 从前一阶段的位置移动到当前位置的次数 dp[i][pos]
                for (auto& prepos : umap[key[i - 1]]) {
                    dp[i][pos] = min(dp[i][pos], dp[i - 1][prepos] + cal(n, prepos, pos) + 1);
                }
            }
        }
        // RETURN 匹配 key[m] 但最终位置落于那个地方不确定
        int res = *min_element(dp[m - 1].begin(), dp[m - 1].end());
        return res;
    }
    // 从 a 到 b 需要的次数 [0, 1, 2, 3, 4, 5]
    // n = 6, 从 2 移动到 4, (6 + 2 - 4) % 6 = 4  (6 + 4 - 2) % 6 = 2
    int cal(int len, int a, int b) {
        return min((len + a - b) % len, (len + b - a) % len);
    }
};

🍺 贪心算法

🍻 区间重叠

🥂 🌸 252. 会议室 [区间数组] [重叠] (贪心)

// 其实就是判断是否存在重叠
class Solution {
private:
    int cur_end = INT_MIN;  // 当前和前一个的开始值
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        // 开始遍历
        for (auto& interval : intervals) {
            int start = interval[0], end = interval[1];
            // 有重叠
            if (start < cur_end) return false;
            // 无重叠
            cur_end = end; 
        }
        return true;
    }
};

🥂 🌸 253. 会议室Ⅱ [区间数组] [重叠] (贪心)

// 求同一个时间点, 最多有几个区间重叠
class Solution {
private:
    vector<int> start;      // 开始的节点
    vector<int> end;        // 结束的节点
    int res= 0, count = 0;  // 最大的重叠数, 当前重叠数
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = intervals.size();
        for (auto& interval : intervals) {
            start.push_back(interval[0]);
            end.push_back(interval[1]);
        }
        // 添加并排序
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        // 开始遍历, start 起点肯定先遍历完
        int i = 0, j = 0;
        while (i < n) {
            if (start[i] < end[j]) {    // 找到开始点
                count++;
                i++;
            } else {                    // 找到结束点, 或重合点, 重叠数都会减
                count--;
                j++;
            }
            res = max(res, count);
        }
        return res;
    }
};

🥂 435. 无重叠区间 [区间数组] [重叠] (贪心)

class Solution {
private:
    int count = 0;          // 记录区间的数量
    int cur_end = INT_MIN;        // 记录当前区间结束的时间
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        // 开始一个个遍历
        for (auto& interval : intervals) {
            int start = interval[0], end = interval[1];
            // 需要移除区间
            if (start < cur_end) {
                count++;
                continue;
            }
            cur_end = end;
        }
        return count;
    }
};

🥂 452. 用最少数量的箭引爆气球 [区间数组] > [非重合区间] > (贪心)

// [区间数组] > [非重合区间] > (贪心) 
class Solution {
private:
    int res = 0;                // 需要射的最少的箭数
    long cur_end = LONG_MIN;    // 上一个区间的 end [-wq, INT_MIN]
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // 按 end 排序
        sort (points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        // 开始遍历一个个区间
        for (auto& point : points) {
            int start = point[0], end = point[1];
            // 碰到重叠区域, 这题擦边也可以射气球
            if (start <= cur_end) continue;
            // 没碰到重叠区域
            res++;
            cur_end = end;
        }
        return res;
    }
};

🥂 1024. 视频拼接 [区间数组] [重叠] (贪心)

// 从 0 开始拼接, 之后在与当前区间重叠的区间中选 end 最大的区间
class Solution {
private:
    int res = 0;    // 需要的视频数
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        int n = clips.size();
        sort(clips.begin(), clips.end(), [](vector<int>& a, vector<int>& b) {
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });
        if (clips[0][0] != 0) return -1;
        if (n == 1 && clips[0][1] != time) return -1;
        // 开始遍历
        int cur_end = 0, next_end = 0;          // 当前 end, 下一个临时 end
        int i = 0;                              // 第 i 个视频
        while (i < n && clips[i][0] <= cur_end) {
            // 找下一个有重复区间的视频
            while (i < n && clips[i][0] <= cur_end) {
                // 选这两个符合条件的其中的最大 end 值
                next_end = max(next_end, clips[i][1]);
                i++;
            }
            // 此时已经找到合适的视频了
            res++;
            cur_end = next_end;
            if (cur_end >= time) return res;
        }
        // 找不到
        return -1;
    }
};

🍻 跳跃

🥂 🌸 45. 跳跃游戏II [数组] [跳跃] (贪心)

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int end = 0;                // 当前可以跳的位置 [1, 2, 3]
        int jump = 0;               // 跳的次数
        int far = 0;                // 可以跳的最远的距离
        // 开始跳
        for (int i = 0; i < n - 1; ++i) {
            far = max(far, i + nums[i]);        // 可以跳的最远距离
            if (i == end) {                     // 到达最远距离后, 获取下一次最远距离
                jump++;
                end = far;
            }
        }
        return jump;
    }
};

🥂 🌸 55. 跳跃游戏 [数组] [跳跃] (贪心)

// 每一步都往最远了跳
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int far = 0;        // 最远跳的距离
        for (int i = 0; i < n - 1; ++i) {
            far = max(far, i + nums[i]);
            if (far <= i) return false;
        }
        // 判断能跳过去不
        if (far < n - 1) return false;
        return true;
    }
};

🍻 子序列和

🥂 1090. 受标签影响的最大值 [映射数组] > [子序列和] > (贪心)

// [映射数组] > [子序列和] > (贪心)
class Solution {
private:
    vector<pair<int, int>> pairs;               // 记录初始值对应的下标索引
    unordered_map<int, int> umap;               // 记录标签情况 
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        int n = values.size();
        int res = 0, num = 0;                   // 总结果, 数字个数
        pairs = vector<pair<int, int>>(n);
        for (int i = 0; i < n; ++i) {
            pairs[i] = make_pair(values[i], labels[i]);
        }
        // 按照 values 排序
        sort(pairs.begin(), pairs.end(), [](pair<int, int>& a, pair<int, int>& b) {
            return a.first > b.first;
        });
        // 贪心, 一个个拿
        for (int i = 0; i < n && num < numWanted; ++i) {
            int cur_v = pairs[i].first, cur_l = pairs[i].second;
            if (umap[cur_l] < useLimit) {
                umap[cur_l]++;
                num++;
                res += cur_v;
            }
        }
        return res;
    }
};

文章来源地址https://www.toymoban.com/news/detail-797052.html

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

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

领支付宝红包 赞助服务器费用

相关文章

  • 背包问题算法全解析:动态规划和贪心算法详解

    计算机背包问题是动态规划算法中的经典问题。本文将从理论和实践两个方面深入探讨计算机背包问题,并通过实际案例分析,帮助读者更好地理解和应用该问题。 背包问题是一种经典的优化问题。有的时候我们需要将有一堆不同重量或者体积的物品放入背包,但是背包容量

    2024年02月09日
    浏览(49)
  • 数据结构与算法之贪心&动态规划

            一:思考         1.某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束 时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?电影的话 那肯定是最多加票价最高的,入场

    2024年02月09日
    浏览(47)
  • 算法设计与分析实验:动态规划与贪心

    目录 一、零钱兑换 1.1 思路一:动态规划 1.2 思路二:贪心 二、安排工作以达到最大效益 2.1 具体思路 2.2 思路呈现 2.3 代码实现 2.4 复杂度分析 2.5 运行结果 三、雇佣k名工人的最低成本 3.1 具体思路 3.2 思路展示 3.3 代码实现 3.4 复杂度分析 3.5 运行结果 结尾语 “生活有意思的

    2024年02月19日
    浏览(64)
  • “算法详解”系列第3卷贪心算法和动态规划出版

    “算法详解”系列图书共有4卷,目前1到3卷已经出版。最新出版的是第3卷—贪心算法和动态规划。 “算法详解”系列图书共有4卷,本书是第3卷—贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、集群、哈夫曼编码等,动态规划主要包括背包、序列对齐、最短

    2024年02月13日
    浏览(34)
  • 01背包(动态规划,贪心算法,回溯法,分支限界法)

    有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? number=4,capacity=8 物品编号(i) W(体积) V(价值) 1 2 3 2 3 4 3 4 5 4 5 6 1.什么是动态规划 1.动态规划算法是通过拆分问题,定义问题状态和状态之间的关系, 使得

    2024年02月08日
    浏览(67)
  • 五大常用算法——分治法,动态规划,回溯法,分支界限法,贪心算法

    (1) 分治法 将一个难以直接解决的大问题,分割成一些规模较小的相同问题 快速排序 快排也是分治的一个实例,快排每一趟会选定一个数,将比这个数小的放左面,比这个数大的放右面, 然后递归分治求解两个子区间,当然快排因为在分的时候就做了很多工作, 当全部分到

    2024年02月04日
    浏览(39)
  • 华为OD机试题中 动态规划和贪心算法例题

    在 ACM 比赛中,有许多常见的编程算法和数据结构经常被使用。本系列博客会罗列各种常见算法,以及其代表性例题。 这部分内容可以用于类似华为 OD 机考学习。 动态规划是一种将复杂问题分解为简单子问题并使用子问题的解来构建更大问题的方法。它通常用于解决最长公

    2024年01月16日
    浏览(45)
  • (软考-软件设计师.下午)动态规划算法、回溯算法、贪心算法、分治算法的应用

    :【递归技术】【二分查找】 分治法的设计思路: 将一个难以直接解决的 大问题 分解成一些 规模较小 的相同问题以便于 逐个击破,分而治之 。      由代码可以看出二分查找也属于分治法的一种,关于二分查找,这位博主总结的很详细。  :【查表】   动

    2024年02月06日
    浏览(71)
  • 【地铁上的面试题】--基础部分--数据结构与算法--动态规划和贪心算法

    一、动态规划的基本概念和思想 1.1 动态规划的定义和特点 动态规划是一种解决多阶段决策问题的算法思想,它通过将问题划分为若干个子问题,并保存子问题的解来求解原问题的方法。动态规划的特点包括以下几个方面: 最优子结构性质:动态规划问题具有最优子结构,即

    2024年02月12日
    浏览(54)
  • 算法思想—枚举、递推、迭代、递归、分治、贪心、动态规划、回溯、模拟、分支定界

    算法思想 枚举(暴力算法) 枚举算法(暴力算法)是一种通过逐一尝试所有可能解来解决问题的算法。它的基本思想是将问题的所有可能答案一一列举出来,并根据一定的判断条件来确定哪些答案是合适的。这种算法通常使用循环来实现,因为需要尝试所有可能的情况。两

    2024年02月01日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包