AI 助理
备案控制台
开发者社区 人工智能 文章 正文

class069 从递归入手三维动态规划【算法】

2023-12-21 65
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： class069 从递归入手三维动态规划【算法】

class069 从递归入手三维动态规划

code1 474. 一和零

// 一和零(多维费用背包)

// 给你一个二进制字符串数组 strs 和两个整数 m 和 n

// 请你找出并返回 strs 的最大子集的长度

// 该子集中 最多 有 m 个 0 和 n 个 1

// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集

// 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/

dp[i][o][z]：表示str[i…]之后选取不超过o z的子集数量

=max(不选该串，选该串)

不选该串：dp[i+1][o][z]

选该串：1+dp[i+1][o-os][z-zs]

code1 递归

code2 记忆化搜索

code3 动态规划

code4 空间压缩

package class069;
// 一和零(多维费用背包)
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n
// 请你找出并返回 strs 的最大子集的长度
// 该子集中 最多 有 m 个 0 和 n 个 1
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
// 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/
public class Code01_OnesAndZeroes {
  public static int zeros, ones;
  // 统计一个字符串中0的1的数量
  // 0的数量赋值给全局变量zeros
  // 1的数量赋值给全局变量ones
  public static void zerosAndOnes(String str) {
    zeros = 0;
    ones = 0;
    for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '0') {
        zeros++;
      } else {
        ones++;
      }
    }
  }
  public static int findMaxForm1(String[] strs, int m, int n) {
    return f1(strs, 0, m, n);
  }
  // strs[i....]自由选择，希望零的数量不超过z、一的数量不超过o
  // 最多能选多少个字符串
  public static int f1(String[] strs, int i, int z, int o) {
    if (i == strs.length) {
      // 没有字符串了
      return 0;
    }
    // 不使用当前的strs[i]字符串
    int p1 = f1(strs, i + 1, z, o);
    // 使用当前的strs[i]字符串
    int p2 = 0;
    zerosAndOnes(strs[i]);
    if (zeros <= z && ones <= o) {
      p2 = 1 + f1(strs, i + 1, z - zeros, o - ones);
    }
    return Math.max(p1, p2);
  }
  // 记忆化搜索
  public static int findMaxForm2(String[] strs, int m, int n) {
    int[][][] dp = new int[strs.length][m + 1][n + 1];
    for (int i = 0; i < strs.length; i++) {
      for (int z = 0; z <= m; z++) {
        for (int o = 0; o <= n; o++) {
          dp[i][z][o] = -1;
        }
      }
    }
    return f2(strs, 0, m, n, dp);
  }
  public static int f2(String[] strs, int i, int z, int o, int[][][] dp) {
    if (i == strs.length) {
      return 0;
    }
    if (dp[i][z][o] != -1) {
      return dp[i][z][o];
    }
    int p1 = f2(strs, i + 1, z, o, dp);
    int p2 = 0;
    zerosAndOnes(strs[i]);
    if (zeros <= z && ones <= o) {
      p2 = 1 + f2(strs, i + 1, z - zeros, o - ones, dp);
    }
    int ans = Math.max(p1, p2);
    dp[i][z][o] = ans;
    return ans;
  }
  public static int findMaxForm3(String[] strs, int m, int n) {
    int len = strs.length;
    int[][][] dp = new int[len + 1][m + 1][n + 1];
    for (int i = len - 1; i >= 0; i--) {
      zerosAndOnes(strs[i]);
      for (int z = 0, p1, p2; z <= m; z++) {
        for (int o = 0; o <= n; o++) {
          p1 = dp[i + 1][z][o];
          p2 = 0;
          if (zeros <= z && ones <= o) {
            p2 = 1 + dp[i + 1][z - zeros][o - ones];
          }
          dp[i][z][o] = Math.max(p1, p2);
        }
      }
    }
    return dp[0][m][n];
  }
  public static int findMaxForm4(String[] strs, int m, int n) {
    // 代表i == len
    int[][] dp = new int[m + 1][n + 1];
    for (String s : strs) {
      // 每个字符串逐渐遍历即可
      // 更新每一层的表
      // 和之前的遍历没有区别
      zerosAndOnes(s);
      for (int z = m; z >= zeros; z--) {
        for (int o = n; o >= ones; o--) {
          dp[z][o] = Math.max(dp[z][o], 1 + dp[z - zeros][o - ones]);
        }
      }
    }
    return dp[m][n];
  }
}

code2 879. 盈利计划

// 盈利计划(多维费用背包)

// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润

// 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与

// 如果成员参与了其中一项工作，就不能参与另一项工作

// 工作的任何至少产生 minProfit 利润的子集称为 盈利计划

// 并且工作的成员总数最多为 n

// 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

// 测试链接 : https://leetcode.cn/problems/profitable-schemes/

dp[i][r][s]：表示工作[i…]之后人数剩余r，利润剩余s的方案数

code1 递归

code2 记忆化搜索

code3 动态规划+空间压缩

package class069;
// 盈利计划(多维费用背包)
// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润
// 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与
// 如果成员参与了其中一项工作，就不能参与另一项工作
// 工作的任何至少产生 minProfit 利润的子集称为 盈利计划
// 并且工作的成员总数最多为 n
// 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
// 测试链接 : https://leetcode.cn/problems/profitable-schemes/
public class Code02_ProfitableSchemes {
  // n : 员工的额度，不能超
  // p : 利润的额度，不能少
  // group[i] : i号项目需要几个人
  // profit[i] : i号项目产生的利润
  // 返回能做到员工不能超过n，利润不能少于p的计划有多少个
  public static int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
    return f1(group, profit, 0, n, minProfit);
  }
  // i : 来到i号工作
  // r : 员工额度还有r人，如果r<=0说明已经没法再选择工作了
  // s : 利润还有s才能达标，如果s<=0说明之前的选择已经让利润达标了
  // 返回 : i.... r、s，有多少种方案
  public static int f1(int[] g, int[] p, int i, int r, int s) {
    if (r <= 0) {
      // 人已经耗尽了，之前可能选了一些工作
      return s <= 0 ? 1 : 0;
    }
    // r > 0
    if (i == g.length) {
      // 工作耗尽了，之前可能选了一些工作
      return s <= 0 ? 1 : 0;
    }
    // 不要当前工作
    int p1 = f1(g, p, i + 1, r, s);
    // 要做当前工作
    int p2 = 0;
    if (g[i] <= r) {
      p2 = f1(g, p, i + 1, r - g[i], s - p[i]);
    }
    return p1 + p2;
  }
  public static int mod = 1000000007;
  public static int profitableSchemes2(int n, int minProfit, int[] group, int[] profit) {
    int m = group.length;
    int[][][] dp = new int[m][n + 1][minProfit + 1];
    for (int a = 0; a < m; a++) {
      for (int b = 0; b <= n; b++) {
        for (int c = 0; c <= minProfit; c++) {
          dp[a][b][c] = -1;
        }
      }
    }
    return f2(group, profit, 0, n, minProfit, dp);
  }
  public static int f2(int[] g, int[] p, int i, int r, int s, int[][][] dp) {
    if (r <= 0) {
      return s == 0 ? 1 : 0;
    }
    if (i == g.length) {
      return s == 0 ? 1 : 0;
    }
    if (dp[i][r][s] != -1) {
      return dp[i][r][s];
    }
    int p1 = f2(g, p, i + 1, r, s, dp);
    int p2 = 0;
    if (g[i] <= r) {
      p2 = f2(g, p, i + 1, r - g[i], Math.max(0, s - p[i]), dp);
    }
    int ans = (p1 + p2) % mod;
    dp[i][r][s] = ans;
    return ans;
  }
  public static int profitableSchemes3(int n, int minProfit, int[] group, int[] profit) {
    // i = 没有工作的时候，i == g.length
    int[][] dp = new int[n + 1][minProfit + 1];
    for (int r = 0; r <= n; r++) {
      dp[r][0] = 1;
    }
    int m = group.length;
    for (int i = m - 1; i >= 0; i--) {
      for (int r = n; r >= 0; r--) {
        for (int s = minProfit; s >= 0; s--) {
          int p1 = dp[r][s];
          int p2 = group[i] <= r ? dp[r - group[i]][Math.max(0, s - profit[i])] : 0;
          dp[r][s] = (p1 + p2) % mod;
        }
      }
    }
    return dp[n][minProfit];
  }
}

code3 688. 骑士在棋盘上的概率

// 骑士在棋盘上的概率

// n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动

// 行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1)

// 象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格

// 每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里

// 骑士继续移动，直到它走了 k 步或离开了棋盘

// 返回 骑士在棋盘停止移动后仍留在棋盘上的概率

// 测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/

code 记忆化搜索

package class069;
// 骑士在棋盘上的概率
// n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动
// 行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1)
// 象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格
// 每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里
// 骑士继续移动，直到它走了 k 步或离开了棋盘
// 返回 骑士在棋盘停止移动后仍留在棋盘上的概率 
// 测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/
public class Code03_KnightProbabilityInChessboard {
  public static double knightProbability(int n, int k, int row, int col) {
    double[][][] dp = new double[n][n][k + 1];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int t = 0; t <= k; t++) {
          dp[i][j][t] = -1;
        }
      }
    }
    return f(n, row, col, k, dp);
  }
  // 从(i,j)出发还有k步要走，返回最后在棋盘上的概率
  public static double f(int n, int i, int j, int k, double[][][] dp) {
    if (i < 0 || i >= n || j < 0 || j >= n) {
      return 0;
    }
    if (dp[i][j][k] != -1) {
      return dp[i][j][k];
    }
    double ans = 0;
    if (k == 0) {
      ans = 1;
    } else {
      ans += (f(n, i - 2, j + 1, k - 1, dp) / 8);
      ans += (f(n, i - 1, j + 2, k - 1, dp) / 8);
      ans += (f(n, i + 1, j + 2, k - 1, dp) / 8);
      ans += (f(n, i + 2, j + 1, k - 1, dp) / 8);
      ans += (f(n, i + 2, j - 1, k - 1, dp) / 8);
      ans += (f(n, i + 1, j - 2, k - 1, dp) / 8);
      ans += (f(n, i - 1, j - 2, k - 1, dp) / 8);
      ans += (f(n, i - 2, j - 1, k - 1, dp) / 8);
    }
    dp[i][j][k] = ans;
    return ans;
  }
}

code4 2435. 矩阵中和能被 K 整除的路径

// 矩阵中和能被 K 整除的路径

// 给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k

// 从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)

// 请你返回路径和能被 k 整除的路径数目

// 由于答案可能很大，返回答案对10^9+7取余的结果

// 测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/

code1 递归

code2 记忆化搜索

code3 动态规划

package class069;
// 矩阵中和能被 K 整除的路径
// 给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k
// 从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)
// 请你返回路径和能被 k 整除的路径数目
// 由于答案可能很大，返回答案对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/
public class Code04_PathsDivisibleByK {
  public static int mod = 1000000007;
  public static int numberOfPaths1(int[][] grid, int k) {
    int n = grid.length;
    int m = grid[0].length;
    return f1(grid, n, m, k, 0, 0, 0);
  }
  // 当前来到(i,j)位置，最终一定要走到右下角(n-1,m-1)
  // 从(i,j)出发，最终一定要走到右下角(n-1,m-1)，有多少条路径，累加和%k的余数是r
  public static int f1(int[][] grid, int n, int m, int k, int i, int j, int r) {
    if (i == n - 1 && j == m - 1) {
      return grid[i][j] % k == r ? 1 : 0;
    }
    // 后续需要凑出来的余数need
    int need = (k + r - (grid[i][j] % k)) % k;
    int ans = 0;
    if (i + 1 < n) {
      ans = f1(grid, n, m, k, i + 1, j, need);
    }
    if (j + 1 < m) {
      ans = (ans + f1(grid, n, m, k, i, j + 1, need)) % mod;
    }
    return ans;
  }
  public static int numberOfPaths2(int[][] grid, int k) {
    int n = grid.length;
    int m = grid[0].length;
    int[][][] dp = new int[n][m][k];
    for (int a = 0; a < n; a++) {
      for (int b = 0; b < m; b++) {
        for (int c = 0; c < k; c++) {
          dp[a][b][c] = -1;
        }
      }
    }
    return f2(grid, n, m, k, 0, 0, 0, dp);
  }
  public static int f2(int[][] grid, int n, int m, int k, int i, int j, int r, int[][][] dp) {
    if (i == n - 1 && j == m - 1) {
      return grid[i][j] % k == r ? 1 : 0;
    }
    if (dp[i][j][r] != -1) {
      return dp[i][j][r];
    }
    int need = (k + r - grid[i][j] % k) % k;
    int ans = 0;
    if (i + 1 < n) {
      ans = f2(grid, n, m, k, i + 1, j, need, dp);
    }
    if (j + 1 < m) {
      ans = (ans + f2(grid, n, m, k, i, j + 1, need, dp)) % mod;
    }
    dp[i][j][r] = ans;
    return ans;
  }
  public static int numberOfPaths3(int[][] grid, int k) {
    int n = grid.length;
    int m = grid[0].length;
    int[][][] dp = new int[n][m][k];
    dp[n - 1][m - 1][grid[n - 1][m - 1] % k] = 1;
    for (int i = n - 2; i >= 0; i--) {
      for (int r = 0; r < k; r++) {
        dp[i][m - 1][r] = dp[i + 1][m - 1][(k + r - grid[i][m - 1] % k) % k];
      }
    }
    for (int j = m - 2; j >= 0; j--) {
      for (int r = 0; r < k; r++) {
        dp[n - 1][j][r] = dp[n - 1][j + 1][(k + r - grid[n - 1][j] % k) % k];
      }
    }
    for (int i = n - 2, need; i >= 0; i--) {
      for (int j = m - 2; j >= 0; j--) {
        for (int r = 0; r < k; r++) {
          need = (k + r - grid[i][j] % k) % k;
          dp[i][j][r] = dp[i + 1][j][need];
          dp[i][j][r] = (dp[i][j][r] + dp[i][j + 1][need]) % mod;
        }
      }
    }
    return dp[0][0][0];
  }
}

code5 87. 扰乱字符串

// 扰乱字符串

// 使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

// 步骤1 : 如果字符串的长度为 1 ，算法停止

// 步骤2 : 如果字符串的长度 > 1 ，执行下述步骤：

// 在一个随机下标处将字符串分割成两个非空的子字符串

// 已知字符串s，则可以将其分成两个子字符串x和y且满足s=x+y

// 可以决定是要 交换两个子字符串 还是要 保持这两个子字符串的顺序不变

// 即s可能是 s = x + y 或者 s = y + x

// 在x和y这两个子字符串上继续从步骤1开始递归执行此算法

// 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串

// 如果是，返回true ；否则，返回false

// 测试链接 : https://leetcode.cn/problems/scramble-string/

code1 递归

code2 递归优化

code3 记忆化搜索

code4 动态规划

package class069;
// 扰乱字符串
// 使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
// 步骤1 : 如果字符串的长度为 1 ，算法停止
// 步骤2 : 如果字符串的长度 > 1 ，执行下述步骤：
//        在一个随机下标处将字符串分割成两个非空的子字符串
//        已知字符串s，则可以将其分成两个子字符串x和y且满足s=x+y
//        可以决定是要 交换两个子字符串 还是要 保持这两个子字符串的顺序不变
//        即s可能是 s = x + y 或者 s = y + x
//        在x和y这两个子字符串上继续从步骤1开始递归执行此算法
// 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串
// 如果是，返回true ；否则，返回false
// 测试链接 : https://leetcode.cn/problems/scramble-string/
public class Code05_ScrambleString {
  public static boolean isScramble1(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    return f1(s1, 0, n - 1, s2, 0, n - 1);
  }
  // s1[l1....r1]
  // s2[l2....r2]
  // 保证l1....r1与l2....r2
  // 是不是扰乱串的关系
  public static boolean f1(char[] s1, int l1, int r1, char[] s2, int l2, int r2) {
    if (l1 == r1) {
      // s1[l1..r1]
      // s2[l2..r2]
      return s1[l1] == s2[l2];
    }
    // s1[l1..i][i+1....r1]
    // s2[l2..j][j+1....r2]
    // 不交错去讨论扰乱关系
    for (int i = l1, j = l2; i < r1; i++, j++) {
      if (f1(s1, l1, i, s2, l2, j) && f1(s1, i + 1, r1, s2, j + 1, r2)) {
        return true;
      }
    }
    // 交错去讨论扰乱关系
    // s1[l1..........i][i+1...r1]
    // s2[l2...j-1][j..........r2]
    for (int i = l1, j = r2; i < r1; i++, j--) {
      if (f1(s1, l1, i, s2, j, r2) && f1(s1, i + 1, r1, s2, l2, j - 1)) {
        return true;
      }
    }
    return false;
  }
  // 依然暴力尝试，只不过四个可变参数，变成了三个
  public static boolean isScramble2(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    return f2(s1, s2, 0, 0, n);
  }
  public static boolean f2(char[] s1, char[] s2, int l1, int l2, int len) {
    if (len == 1) {
      return s1[l1] == s2[l2];
    }
    // s1[l1.......]  len
    // s2[l2.......]  len
    // 左 : k个   右: len - k 个
    for (int k = 1; k < len; k++) {
      if (f2(s1, s2, l1, l2, k) && f2(s1, s2, l1 + k, l2 + k, len - k)) {
        return true;
      }
    }
    // 交错！
    for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) {
      if (f2(s1, s2, l1, j, k) && f2(s1, s2, i, l2, len - k)) {
        return true;
      }
    }
    return false;
  }
  public static boolean isScramble3(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    // dp[l1][l2][len] : int 0 -> 没展开过
    // dp[l1][l2][len] : int -1 -> 展开过，返回的结果是false
    // dp[l1][l2][len] : int 1 -> 展开过，返回的结果是true
    int[][][] dp = new int[n][n][n + 1];
    return f3(s1, s2, 0, 0, n, dp);
  }
  public static boolean f3(char[] s1, char[] s2, int l1, int l2, int len, int[][][] dp) {
    if (len == 1) {
      return s1[l1] == s2[l2];
    }
    if (dp[l1][l2][len] != 0) {
      return dp[l1][l2][len] == 1;
    }
    boolean ans = false;
    for (int k = 1; k < len; k++) {
      if (f3(s1, s2, l1, l2, k, dp) && f3(s1, s2, l1 + k, l2 + k, len - k, dp)) {
        ans = true;
        break;
      }
    }
    if (!ans) {
      for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) {
        if (f3(s1, s2, l1, j, k, dp) && f3(s1, s2, i, l2, len - k, dp)) {
          ans = true;
          break;
        }
      }
    }
    dp[l1][l2][len] = ans ? 1 : -1;
    return ans;
  }
  public static boolean isScramble4(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    boolean[][][] dp = new boolean[n][n][n + 1];
    // 填写len=1层，所有的格子
    for (int l1 = 0; l1 < n; l1++) {
      for (int l2 = 0; l2 < n; l2++) {
        dp[l1][l2][1] = s1[l1] == s2[l2];
      }
    }
    for (int len = 2; len <= n; len++) {
      // 注意如下的边界条件 : l1 <= n - len l2 <= n - len
      for (int l1 = 0; l1 <= n - len; l1++) {
        for (int l2 = 0; l2 <= n - len; l2++) {
          for (int k = 1; k < len; k++) {
            if (dp[l1][l2][k] && dp[l1 + k][l2 + k][len - k]) {
              dp[l1][l2][len] = true;
              break;
            }
          }
          if (!dp[l1][l2][len]) {
            for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) {
              if (dp[l1][j][k] && dp[i][l2][len - k]) {
                dp[l1][l2][len] = true;
                break;
              }
            }
          }
        }
      }
    }
    return dp[0][0][n];
  }
}


文章标签：
算法
机器学习/深度学习
关键词：
动态规划算法
三维算法
递归算法
递归动态规划算法
日星月云
目录
相关文章
修己xj
|
3天前
|
存储 算法 Java
算法系列之动态规划
动态规划（Dynamic Programming，简称DP）是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题，并存储这些子问题的解来避免重复计算，从而提高算法的效率。
修己xj
18 4
算法系列之动态规划
修己xj
|
5天前
|
存储 算法 Java
算法系列之递归反转单链表
递归反转链表的基本思路是将当前节点的next指针指向前一个节点，然后递归地对下一个节点进行同样的操作。递归的核心思想是将问题分解为更小的子问题，直到达到基本情况（通常是链表末尾）。
修己xj
25 5
算法系列之递归反转单链表
羑悻的小杀马特
|
11天前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾：约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾：约瑟夫环问题的奇幻密码
羑悻的小杀马特
16 0
羑悻的小杀马特
|
11天前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭：如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭：如何用算法装满你的 “财富背包”
羑悻的小杀马特
36 0
潜意识Java
|
2月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
潜意识Java
57 5
龙大吉
|
4月前
|
算法 Python
在Python编程中，分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题，递归解决后合并结果
在Python编程中，分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题，递归解决后合并结果；贪心算法在每一步选择局部最优解，追求全局最优；动态规划通过保存子问题的解，避免重复计算，确保全局最优。这三种算法各具特色，适用于不同类型的问题，合理选择能显著提升编程效率。
龙大吉
90 2
java冯坚持
|
5月前
|
算法
动态规划算法学习三：0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解，包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
java冯坚持
180 2
动态规划算法学习三：0-1背包问题
java冯坚持
|
5月前
|
算法
动态规划算法学习四：最大上升子序列问题（LIS：Longest Increasing Subsequence）
这篇文章介绍了动态规划算法中解决最大上升子序列问题（LIS）的方法，包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法，如非动态规划的二分法。
java冯坚持
107 0
动态规划算法学习四：最大上升子序列问题（LIS：Longest Increasing Subsequence）
java冯坚持
|
5月前
|
算法
动态规划算法学习二：最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列（LCS）问题，包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法，以及具体的代码实现。
java冯坚持
225 0
动态规划算法学习二：最长公共子序列
java冯坚持
|
5月前
|
存储 算法
动态规划算法学习一：DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解，包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
java冯坚持
262 0

热门文章

最新文章

  • 1
    DeepSeek加持的通义灵码2.0 AI程序员实战案例：助力嵌入式开发中的算法生成革新
  • 2
    接入DeepSeek需要做算法备案吗？一文读懂算法备案的那些事儿
  • 3
    近端策略优化(PPO)算法的理论基础与PyTorch代码详解
  • 4
    基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
  • 5
    算法系列之分治算法
  • 6
    C 408—《数据结构》算法题基础篇—链表（上）
  • 7
    【算法合规新时代】企业如何把握“清朗·网络平台算法典型问题治理”专项行动？
  • 8
    单纯接入第三方模型就无需算法备案了么？
  • 9
    C 408—《数据结构》算法题基础篇—链表（下）
  • 10
    算法系列之搜索算法-深度优先搜索DFS
  • 1
    量子算法的设计与优化：迈向量子计算的未来
    21
  • 2
    算法系列之排序算法-堆排序
    20
  • 3
    使用 PAI-DSW x Free Prompt Editing图像编辑算法，开发个人AIGC绘图小助理
    12
  • 4
    [ICDE2024]多正常模式感知的频域异常检测算法MACE
    14
  • 5
    监控局域网其他电脑：Go 语言迪杰斯特拉算法的高效应用
    14
  • 6
    关于公司电脑桌面监控中 PHP 二叉搜索树算法的深度剖析
    16
  • 7
    算法系统协同优化，vivo与港中文推出BlueLM-V-3B，手机秒变多模态AI专家
    21
  • 8
    基于GWO灰狼优化的多目标优化算法matlab仿真
    18
  • 9
    算法系列之动态规划
    18
  • 10
    【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
    15

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    通义万相：视觉生成大模型再进化