0%

LeetCode-贪心和动态规划

贪心算法在每一次选择中都选择当下最优解,但只会考虑到眼前的情况,并不一定会得到最优解。

经典例题

有1、5、10、20、50面额的货币,使用尽量少的货币凑出66元。贪心算法50+10+5+1,4张为最优解。
如果面额为1、5、11,使用尽量少的货币凑出15元。贪心算法11+1+1+1+1,使用了5张,但3张为最优解。

1
2
3
4
5
f(15)=f(14)+1=5
f(15)=f(10)+1=3
f(15)=f(4)+1=5

f(n)=min{f(n-1),f(n-5),f(n-11)}+1

这就是动态规划算法,将一个大问题分为几个小问题,分别求小问题的解,即可求解出

leetcode练习

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

贪心算法

为每一步都选择最小的数,结果并不一定正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minimumTotal(List<List<Integer>> triangle) {
int result = 0;
int index = 0;
result += triangle.get(0).get(0);
for(int i = 1 ; i < triangle.size() ; i++){
List<Integer> list = triangle.get(i);
if(list.get(index) > list.get(index + 1)){
index += 1;
}
result += list.get(index);
}
return result;
}

动态规划算法

从上往下,求出到每个点的最短距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minimumTotal(List<List<Integer>> triangle) {
int m = triangle.size();
int[][] arr = new int[m][m];
arr[0][0] = triangle.get(0).get(0);
for(int i = 1 ; i < m ; i++){
arr[i][0] = triangle.get(i).get(0) + arr[i-1][0];
}
for(int i = 1 ; i < m ; i++){
arr[i][i] = triangle.get(i).get(i) + arr[i-1][i-1];
}
for(int i = 2 ; i < m ; i++){
for(int j = 1 ; j < i ; j++){
arr[i][j] = Math.min(arr[i-1][j-1],arr[i-1][j]) + triangle.get(i).get(j);
}
}
int result = arr[m-1][0];
for(int i = 1 ; i <= m-1 ; i++){
result = Math.min(result,arr[m-1][i]);
}
return result;
}