前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
理论基础
动态规划和贪心的区别在于,贪心是以局部最优推出全局最优,只需做到局部最优即可。而动态规划的局部受上一步的影响。举个例子:
贪心:背包容量5,石头大小分别为:1,2,3,4,问怎么拿可以取更多个石头
动态规划:背包容量5,石头大小分别为:1,2,3,4,价值分别为:1,2,1000,3,问怎么拿价值最大
对于贪心,就是假设有一个数组,每次从数组中拿最小的即可,这样就能尽可能多拿石头,且每一步并没有对结果有所影响。
对于动态规划,如果前两次我取了1,2,那么就不能取3,而3的价值很高,可见,前面的选择会影响后面的选择。
习题
1.斐波那契数
题目链接:509. 斐波那契数 - 力扣(LeetCode)
题面:
基本分析:从n=2开始,等于前两个数之和
代码:
class Solution {public int fib(int n) {int a = 0;int b = 1;int ans = 0;if(n==0)return a;else if(n==1)return b;for(int i = 2;i<=n;i++){ans= a+b;a=b;b=ans;}return ans;}
}
2.爬楼梯
题目链接:70. 爬楼梯 - 力扣(LeetCode)
题面:
基本分析:到第n个楼梯的爬法等于n-1的爬法+n-2的爬法
代码:
class Solution {public int climbStairs(int n) {int a=1,b=1,sum=1;for(int i = 2;i<=n;i++){sum=0;sum+=a;sum+=b;a=b;b=sum;}return sum;}}
3.使用最小花费爬楼梯
题目链接:746. 使用最小花费爬楼梯 - 力扣(LeetCode)
题面:
代码:
class Solution {public int minCostClimbingStairs(int[] cost) {int size = cost.length;int[] minCost = new int[size];minCost[0] = 0;minCost[1] = Math.min(cost[0], cost[1]);for (int i = 2; i < size; i++) {minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);}return minCost[size - 1];}
}
4.不同路径
题目链接:62. 不同路径 - 力扣(LeetCode)
题面:
代码:
class Solution {public int uniquePaths(int m, int n) {int[][] f = new int[m][n];f[0][0] = 1;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i > 0 && j > 0) {f[i][j] = f[i - 1][j] + f[i][j - 1];} else if (i > 0) {f[i][j] = f[i - 1][j];} else if (j > 0) {f[i][j] = f[i][j - 1];}}}return f[m - 1][n - 1];}
}
后言
上面是动态规划的基本概念和部分习题,下一篇会有其他习题,希望有所帮助,一同进步,共勉!