算法设计.

文章目录

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

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. 全排列–回溯