井陉网站建设,怎么样自己制作网页,网站外包开发,dw做网站首页怎么做文章目录 1、动态规划2、leetcode509#xff1a;斐波那契数列3、leetcode62#xff1a;不同路径4、leetcode121#xff1a;买卖股票的最佳时机5、leetcode70#xff1a;爬楼梯6、leetcode279#xff1a;完全平方数7、leetcode221#xff1a;最大正方形 1、动态规划
只能… 文章目录 1、动态规划2、leetcode509斐波那契数列3、leetcode62不同路径4、leetcode121买卖股票的最佳时机5、leetcode70爬楼梯6、leetcode279完全平方数7、leetcode221最大正方形 1、动态规划
只能向下、向右的走从图中左上角走到右下角有几条路径 因为只能向下、向右走所以从起始点走到点RC路径数等于以起始点到点RC为对角线的矩形里到点RC左侧点的路径数 到点RC上边点的路径数 动态规划的方程式
// 动态规划的方程式
[RC] [R - 1][C] [R][C - 1]有些类似斐波那契数列了起始点就是[0][0] 动态规划的初始状态那递归终止的条件就是其左侧点或者上边点不存在此时到它的路径只有一条return 1一直算到点RC动态规划的终止状态。以上动态规划的三要素
动态规划的方程式动态规划的初始状态动态规划的终止状态
从起始状态00到终止状态RC中间每个格子的值到达它的路径数都会算出来这些中间结果可存入一个数组这题可用二维数组存。动态规划可用来干
1计数有多少种方式或路径如上面从左上角到右下角有多少路径2求最值从左上角到右下角路径的最大数字和每个数字不等代表权重求最长路径或最小路径3求存在性是否存在某个可能可以从A走到B
动态规划的分类 自底向上从最小的子问题开始逐步计算出所有可能的状态直到解决原问题 自顶向下通过递归地方式从原问题开始依次分解为更小的子问题通常需要记忆化搜索Memoization来保存已经计算过的结果避免重复计算 2、leetcode509斐波那契数列 不再递归了根据方程式步步为营从F(2)一路计算到F(n)并把每个中间值存入数组中最后返回数组的第n个元素即可
public class P509Two {public int recursion(int n) {//F(0)和F(1)if (n 2) {return n 0 ? 0 : 1;}int[] dp new int[n 1];dp[1] 1; //F(1)// 根据方程式计算每个值存入数组从F(2)一路计算到F(5)for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}3、leetcode62不同路径 前面已经分析过了这儿的方程式为F(mn F(m - 1n F(mn - 1初始状态为11终止状态为mn public class P62 {public int uniquePaths(int m, int n) {int[][] dp new int[m][n];dp[0][0] 1;for (int i 0; i m; i) {for (int j 0; j n; j) {// 如果是边缘x轴或者y轴则直接赋值1因为只有一条路可达其余按方程式赋值if (i 0 || j 0) {dp[i][j] 1;} else {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}return dp[m - 1][n - 1];}
}红圈里的这些x轴或者y轴上的到达他们的路径只有一条因此直接赋值1别用方程式去计算会导致数组下标越界。除了这些点其余按方程式赋值最后返回(m-1n-1位置的值即可。
两道题给我的个人感觉是动态规划就是从初始状态开始根据方程式步步为营经过一个个中间状态的值到达终止状态 最后如果你需要存储这些中间状态值一般用数组存储因为其访问数据的时间复杂度为O(1。
4、leetcode121买卖股票的最佳时机 这题本质就是求数组后面元素与前面元素的差值的最大值两层for循环默认返回为0遇到最大的值就覆盖即可 优化下遍历数组更新前 i 天的最低买入成本同时更新前i天的最高利润第i天与前面i-1天最低价的差值然后不停覆盖这个差值取最大值 5、leetcode70爬楼梯 参考上面62题不同路径的思想
62题到mn)的路径数 到mn)上方点的路径数 到mn)左侧点的路径数因为规定了只能向下、向右移动本题到n阶的路径数 到n - 1阶的路径数 到 n - 2阶的路径数因为一次只能走一个或者两个台阶 切入点动态规划要经过状态转移那就该想一下题中要求的状态怎么可以由上一步到达 由此动态规划方程式为
f(n) f(n - 1) f(n - 2)代码实现 6、leetcode279完全平方数 思路一暴力解法 根据四平方和定理这题返回的结果肯定是1、2、3、4里的一个。那我找n是否能由1个平方数搞出来不行就看是否能由2个平方数搞出来最多到4封顶了就。因为这题求的是最少的数量别说n 1 1 1 …… 1。借助以下四条数学规律
实现 7、leetcode221最大正方形
