算法训练营day31

一、贪心算法理论基础

在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

动态规划和贪心的区别

• 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
• 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。

二、分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //先排序，形成升序数组
        Arrays.sort(g);
        Arrays.sort(s);
        int m = g.length, n = s.length;
        int count = 0;
        for(int i = 0, j = 0; i < m && j < n; i++,j++){
        //当前饼干无法满足孩子胃口，饼干大小递增
            while(j < n && g[i] > s[j]){
                j++;
            }
        // g[i] <= s[j]表示饼干能满足孩子胃口
            if(j < n){
                count++;
            }
        }
        return count;
    }
}

三、摆动序列

在循环遍历数组nums的过程中，我们通过比较当前数字和前一个数字的大小关系，来确定当前位置是上升摆动还是下降摆动。

• 如果当前数字大于前一个数字，说明出现了上升摆动。我们更新up的值为down + 1，表示当前位置上升摆动序列的最大长度（因为上升摆动的前一个数字应该是下降摆动序列的最大长度）。
• 如果当前数字小于前一个数字，说明出现了下降摆动。我们更新down的值为up + 1，表示当前位置下降摆动序列的最大长度（因为下降摆动的前一个数字应该是上升摆动序列的最大长度）。

通过不断更新up和down，我们可以找到整个数字序列中的最长摆动子序列的长度。

最后，返回down和up中的最大值，即为最长摆动子序列的长度。

ps，这里的上升和下降其实针对的是序列的尾部两个元素来说的，之前的元素一定都是摆动的序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
//up 和 down 初始化为1，因为一旦找到上升或下降序列，一定是两个元素，+1刚好为2
        int down = 1, up = 1;
//
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return nums.length == 0 ? 0 : Math.max(down, up);
    }
}

四、最大子序和

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
// 1.dp[i] (对应子问题的解) 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0]; //2.初始状态

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];//3.状态转移方程
            } else {
                dp[i] = nums[i];//3.状态转移方程
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

五、零钱兑换(动态规划)

这个题在一定条件下可以使用贪心，但是全部情况的还是要用动态规划，做这个题体验动态规划和贪心算法的区别

只问最优值，没要求最优解，一般情况下可以使用动态规划解决

import java.util.Arrays;

public class Solution {

    public int coinChange(int[] coins, int amount) {
// 给 0 占位，因为索引从0开始，所以dp[amount]对应长度为amount + 1
//用于存储凑齐每个金额所需的最少硬币数量
        int[] dp = new int[amount + 1];

        // 注意：因为要比较的是最小值，这个不可能的值就得赋值成为一个最大值(amount + 1)，用于dp[i]表示无法凑齐对应金额。
        Arrays.fill(dp, amount + 1);

        // 理解 dp[0] = 0 的合理性，单独一枚硬币如果能够凑出面值，符合最优子结构
//将`dp[0]`初始化为0，表示凑齐金额0所需的最少硬币数量为0。
        dp[0] = 0;
//然后，使用两个嵌套的循环进行动态规划计算。外层循环从1到`amount`遍历所有可能的金额。
//内层循环遍历硬币数组`coins`中的每个硬币，判断是否可以使用当前硬币凑齐金额`i`。
//如果可以凑齐，即`i - coin >= 0`，并且凑齐`i - coin`金额所需的最少硬币数量不为`amount + 1`（表示可以凑齐），则更新`dp[i]`为`dp[i - coin]`和`dp[i]`的较小值加1，表示使用当前硬币后的最少硬币数量。通过上述循环，我们得到了凑齐每个金额所需的最少硬币数量。
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != amount + 1) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }

//最后，判断`dp[amount]`是否等于`amount + 1`，如果等于，则表示无法凑齐金额`amount`，将其赋值为-1。
        if (dp[amount] == amount + 1) {
            dp[amount] = -1;
        }
//返回`dp[amount]`作为结果，即为凑齐金额`amount`所需的最少硬币数量（如果无法凑齐则为-1）。
        return dp[amount];
    }
}