算法设计.

文章目录

• 1. 贪心算法：只看当前
• • 1.1 零钱兑换问题：力扣322
  • 2. 活动选择问题
  • 3. 动态规划
  • • 3.1 不同路径：
    • 3.2 0-1背包问题
    • 3.3 完全背包问题
    • 3.4 零钱兑换-动态规划
    • 4. 最长公共字串--动态规划
    • 5. 最长公共子序列
    • 6. 最长递增子序列
    • 7. 打家劫舍
    • 8. 全index.php/tags-41973.html" >���列--回溯

      1. 贪心算法：只看当前

      1.1 零钱兑换问题：力扣322

      用贪心算法：但有可能得到错误的解

      public class Leetcode322 {    public int coinChange(int[] coins, int amount) {        int remainder = amount;        int count = 0;        for (int coin : coins) {            while (remainder - coin > 0) {                remainder -= coin;                count++;            }            if (remainder - coin == 0) {                remainder = 0;                count++;                break;            }        }        if (remainder > 0) {            return -1;        } else {            return count;        }    }    public static void main(String[] args) {        Leetcode322 leetcode = new Leetcode322();        int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);//        int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);//        int count = leetcode.coinChange(new int[]{2}, 3);                // 问题1 没有回头，导致找到更差的解//        int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);          // 问题2 没有回头，导致无解//        int count = leetcode.coinChange(new int[]{15, 10}, 20);          System.out.println(count);    }}

      2. 活动选择问题

      贪心选择：每次选择最早结束的活动

      3. 动态规划

      3.1 不同路径：

      3.2 0-1背包问题

      3.3 完全背包问题

      3.4 零钱兑换-动态规划

      ---

      零钱兑换变种：

      4. 最长公共字串–动态规划

      5. 最长公共子序列

      6. 最长递增子序列

      7. 打家劫舍

      8. 全排列–回溯