1. 贪心
- 贪心能解的题，搜索也可以解
- 贪心只是提高的效率，不保证正确性
860. 柠檬水找零(贪心模板)
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
1 <= bills.length <= 105bills[i]不是5就是10或是20
解题思路
1. 考虑局部的最优达到全局的最优
2. 这题可以用贪心是因为决策具有包容性
20 10 5 ，用这些找零
10 找零 相当于 2*5 找零
20 找零 相当于 10*2 找零 10*1 2*5 找零....
也就是顺序，不管前后顺序，可以走到一个相同的结果
完整代码
/**
* @param {number[]} bills
* @return {boolean}
*/
var lemonadeChange = function(bills) {
let myBills={
5:0,
10:0,
20:0
}
for(let i=0;i<bills.length;i++){
let rtn=bills[i]-5
if(rtn!==0){
// 开始找零，每次找最大的
while(rtn-10>=0&&myBills[10]>0){
myBills[10]--
rtn=rtn-10
}
while(rtn-5>=0&&myBills[5]>0){
myBills[5]--
rtn=rtn-5
}
if(rtn>0){
return false
}
}
myBills[bills[i]]++
}
return true
};
45. 跳跃游戏 II(扩展的贪心模板)
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000
解题思路
1. 预言家
2. 我们不仅仅走一步，我们多看一步，为了达到更好的结果
完整代码
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
// 当前位置
let now=0
// 开始跳跃的最远位置
// 尝试now+1 .... maxLength
// 跳到时，判断当前的pos再次跳到哪里，选取能跳到最远的
let res=0
while(now<nums.length-1){
let maxLength=now+nums[now]
res++
if(maxLength>=(nums.length-1)) break
let max=-1
// 判断跳到第一位置，看能从第一个位置跳到第二个位置最远的
for(let pos=now+1;pos<=maxLength;pos++){
let distance=pos+nums[pos]
if(distance>max){
max=distance
now=pos
}
}
}
return res
};
2. 动态规划(一)
63. 不同路径 II(dfs+记忆化)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
解题思路
1. 遍历所有的状态空间，看每一个是否能到达终点
2. 在1基础上优化
3. 因为每一个点能否到达可以依赖其 右边和下边的点
是否能到达
4. 这些右方和下方的点计算过后，我们记录它是否能到达
这样每个点只需要计算一次
完整代码
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
// 状态空间+记忆化搜索
// 我们遍历所有的网格，看其是否能到达终点
let dx=[0,1]
let dy=[1,0]
let m=obstacleGrid.length
let n=obstacleGrid[0].length
let myArr=new Array(m)
for(let i=0;i<m;i++){
let arr=new Array(n).fill(0)
myArr[i]=arr
}
// console.log(valid)
const dfs=(x,y)=>{
// 越界
if(x>=m||y>=n||x<0||y<0){
return 0
}
// console.log(myArr)
// 有障碍物
if(obstacleGrid[x][y]){
return 0
}
// 到达终点
if(x===m-1&&y===n-1){
return 1
}
// 已经被计算过
if(myArr[x][y]!==0){
return myArr[x][y]
}
// 每个点考虑右方和下方的点能否到达
for(let i=0;i<2;i++){
let nx=x+dx[i]
let ny=y+dy[i]
// console.log(nx,ny)
// console.log(x,y,myArr[0][0])
myArr[x][y]+=dfs(nx,ny)
}
return myArr[x][y]
}
let res=dfs(0,0)
// console.log(myArr[0][0])
return res
// console.log(valid[0][0])
};