devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

面试_动态规划

作者：羊村懒王 | 2024-06-08 22:47:36

赞

踩

dp[j] |= dp[j - num] 是啥意思?

01背包

剑指 Offer II 101. 分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

提示：

  1. 1 <= nums.length <= 200
  2. 1 <= nums[i] <= 100
  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         //nums = [1,5,11,5] -> [1, 11],[5,5] -> true
  5.         int nlen = nums.size();
  6.         if (nlen < 2) {
  7.             return false;
  8.         }
  9.         int total_sum = accumulate(nums.begin(), nums.end(), 0);
  10.         // 和为奇数，肯定不可以拆分
  11.         if (total_sum % 2) {
  12.             return false;
  13.         }
  14.         //找最大值
  15.         int max_sum = *max_element(nums.begin(), nums.end());
  16.         int part_sum = total_sum / 2;
  17.         if (max_sum > part_sum) {
  18.             return false;
  19.         }
  20.         //1. dp代表部分和为i
  21.         // vector<vector<int> > dp(nlen, vector<int>(part_sum + 1, 0));
  22.         // for (int i = 0; i < nlen; ++i) {
  23.         //     dp[i][0] = true;
  24.         // }
  25.         // //第0个数可以构成num[0]的部分和
  26.         // dp[0][nums[0]] = true;
  27.         // for (int i = 1; i < nlen; ++i)
  28.         // {
  29.         //     int num = nums[i];
  30.         //     for (int j = 1; j <= part_sum; ++j)
  31.         //     {
  32.         //         //当前数小于部分和, 不加 | 加当前数
  33.         //         if (nums[i] <= j) {
  34.         //             dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
  35.         //         } else {
  36.         //             dp[i][j] = dp[i - 1][j];
  37.         //         }
  38.         //     }
  39.         // }
  40.         // return dp[nlen - 1][part_sum];
  41.         
  42.         //2. 优化
  43.         vector<int> dp(part_sum + 1, 0);
  44.         dp[0] = true;
  45.         for (int i = 0; i < nlen; ++i)
  46.         {
  47.             int num = nums[i];
  48.             for (int j = part_sum; j >= num; --j)
  49.             {
  50.                 //不加 | 加
  51.                 dp[j] = dp[j] | dp[j - num];
  52.             }
  53.         }
  54.         return dp[part_sum];
  55.     }
  56. };

完全背包

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

  1. 1 <= coins.length <= 12
  2. 1 <= coins[i] <= 231 - 1
  3. 0 <= amount <= 104

法一：动态规划

  1. class Solution:
  2.     def coinChange(self, coins: List[int], amount: int) -> int:
  3.         if amount == 0:
  4.             return 0
  5.         clen = len(coins)
  6.         Max = amount + 1
  7.         dp = [Max for _ in range(amount + 1)]
  8.         dp[0] = 0
  9.         for i in range(1, amount + 1):
  10.             for j in range(0, clen):
  11.                 if coins[j] <= i:
  12.                     dp[i] = min(dp[i], dp[i - coins[j]] + 1)
  13.         
  14.         return dp[amount] if dp[amount] <= amount else -1

法二：记忆化搜索

  1. class Solution {
  2.    vector<int> count;
  3.    int dp(vector<int>& coins, int rest_amount)
  4.    {
  5.         if (rest_amount < 0) return -1;
  6.         if (rest_amount == 0) return 0;
  7.         //如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次
  8.         if (count[rest_amount - 1] != 0) return count[rest_amount - 1];
  9.         int Min = INT_MAX;
  10.         for (int coin : coins)
  11.         {
  12.             //重复选
  13.             int res = dp(coins, rest_amount - coin);
  14.             if (res >= 0 && res < Min) {
  15.                 Min = res + 1;
  16.             }
  17.         }
  18.         count[rest_amount - 1] = (Min == INT_MAX ? -1 : Min);
  19.         return count[rest_amount - 1];
  20.    }
  21. public:
  22.     int coinChange(vector<int>& coins, int amount) {
  23.         if (amount < 1) return 0;
  24.         //count为0~amount所需要的最小硬币数
  25.         count.resize(amount);
  26.         return dp(coins, amount);
  27.     }
  28. };

python写法：使用 @functools.lru_cache(max_len)

  1. class Solution:
  2.     def coinChange(self, coins: List[int], amount: int) -> int:
  3.         # 2. 记忆化搜索
  4.         @functools.lru_cache(amount)
  5.         def dp(rest_amount):
  6.             if rest_amount < 0: return -1
  7.             if rest_amount == 0: return 0
  8.             mini = int(1e9)
  9.             for coin in coins:
  10.                 res = dp(rest_amount - coin)
  11.                 if res >= 0 and res < mini:
  12.                     mini = res + 1
  13.             return mini if mini < int(1e9) else -1
  14.         
  15.         if amount < 1: return 0
  16.         return dp(amount)

一、简单DP

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28
示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下
    示例 3：

输入：m = 7, n = 3
输出：28
示例 4：

输入：m = 3, n = 3
输出：6

提示：

  1. 1 <= m, n <= 100
  2. 题目数据保证答案小于等于 2 * 109
  1. class Solution {
  2.     int ans;
  3. public:
  4.     // 1. dfs：超时
  5.     // void dfs(int i, int j, int m, int n)
  6.     // {
  7.     //     if (i < 0 || i == m || j < 0 || j == n) {
  8.     //         return;
  9.     //     }
  10.     //     if (i == m - 1 && j == n - 1) {
  11.     //         ans += 1;
  12.     //         return;
  13.     //     }
  14.  
  15.     //     int dirs[][2] = {
  16.    {0, 1}, {1, 0}};
  17.     //     for (int k = 0; k < 2; k++)
  18.     //     {
  19.     //         int x = i + dirs[k][0], y = j + dirs[k][1];
  20.     //         if (x < 0 || x == m || y < 0 || y == n) {
  21.     //             continue;
  22.     //         }
  23.     //         dfs(x, y, m, n);
  24.     //     }
  25.     // }
  26.     // int uniquePaths(int m, int n) {
  27.     //     dfs(0, 0, m, n);
  28.     //     return ans;
  29.     // }
  30.     //2. 动态规划: O(n^2)
  31.     // int uniquePaths(int m, int n)
  32.     // {
  33.     //     vector<vector<int> > dp(m + 1, vector<int>(n + 1));
  34.     //     for (int i = 0; i < m; ++i) {
  35.     //         dp[i][0] = 1;
  36.     //     }
  37.     //     for (int j = 0; j < n; ++j) {
  38.     //         dp[0][j] = 1;
  39.     //     }
  40.     //     for (int i = 1; i < m; ++i)
  41.     //     {
  42.     //         for (int j = 1; j < n; ++j)
  43.     //         {
  44.     //             dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  45.     //         }
  46.     //     }
  47.     //     return dp[m - 1][n - 1];
  48.     // }
  49.  
  50.     // O(m)
  51.     int uniquePaths(int m, int n)
  52.     {
  53.         // C(m + n - 2, m - 1): m + n - 2次移动，有m-1次向下，n-1次向右。因此路径总数
  54.         long long ans = 1;
  55.         for (int x = n, y = 1; y < m; ++x, ++y)
  56.         {
  57.             ans = ans * x / y;
  58.         }
  59.         return ans;
  60.     }
  61. };

动态规划：时间复杂度O(n2),空间复杂度O(n2)
组合数：时间复杂度O(m), 空间O(1)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/691529
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号