第六周

贪心算法
取第一步后不断置换
int maxProfit(int* prices, int pricesSize) {
if (pricesSize <= 0) {
return 0;
}

int maxProfit = 0;
int minPrice = prices[0];

for (int i = 0; i < pricesSize; i++) {
    if (prices[i] < minPrice) {
        minPrice = prices[i];
    } else {
        int currentProfit = prices[i] - minPrice;
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit;
        }
    }
}

return maxProfit;

}
bool canJump(int* nums, int numsSize){
int max_reach = 0; // 最远可以到达的位置

for (int i = 0; i < numsSize; i++) {
    // 如果当前位置不可达，直接返回False
    if (i > max_reach) {
        return false;
    }

    // 更新最远可以到达的位置
    max_reach = (i + nums[i] > max_reach) ? (i + nums[i]) : max_reach;

    // 如果最远可以到达的位置已经超过或等于最后一个下标，返回True
    if (max_reach >= numsSize - 1) {
        return true;
    }
}

return true;

}
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n]; // dp[i] 表示跳到位置 i 的最小跳跃数

// 初始化 dp 数组
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0; // 初始位置的最小跳跃数为 0

for (int i = 0; i < n; i++) {
    int maxJump = Math.min(i + nums[i], n - 1); // 当前位置可以跳到的最远位置
    for (int j = i + 1; j <= maxJump; j++) {
        dp[j] = Math.min(dp[j], dp[i] + 1); // 更新跳到 j 的最小跳跃数
    }
}

return dp[n - 1];

}

}