爬楼梯
爬楼梯
原题链接:https://leetcode.cn/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
1.递推与递归==思路==:简单的递推问题(斐波那契数列)
到达第一阶梯的方法数为1
到达第二阶梯的方法数为1
到达第三阶梯的方法数为 第一阶梯的方法数 + 第二阶梯的方法数
……
到达第n阶梯的方法数为 第 n - 1 阶梯的方法数 + 第 n - 2 阶梯的方法数
ans[i] = ans[i - 1] + ans[i - 2];
1234567891011121314class Solution {public: int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int ans[2] = {1, 2}; int a = 0, b = 1; for (int i = 3; i <= n; ++i) { ans[a] += ans[b]; swap(a, b); } return ans[b]; }};
最大子数组和
最大子数组和
原题链接:https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。
12345678class Solution {public: int maxSubArray(vector<int>& nums) { int final = nums[0], ans = nums[0]; ans = max(nums[i], ans + nums[i]); fin = max(fin, ans); }};
这是一道典型的使用「动态规划」解决的问题,需要我们掌握动态规划问题设计状态的技巧(无后效性),
并且需要知道如何推导状态转移方程,最后再去优化空间。
1.动态规划step1问题理解「力扣」第 53 题(最大子序和)是「力扣」第 124 题(二叉树的最大路径和)的线性版本,它们的状态设计思想和状态转移是类似的,希望大家能够通过本题题解进一步体会状态是如何想到的(即子问题的定义需要从哪些方面考虑)。
本题接的重点在「关键 1:理解题意」和「关键 2:如何定义子问题(如何定义状态)」和「最后再谈谈「无后效性」。
关键 1:理解题意
题目要我们找出和最大的连续子数组的值是多少,「连续」是关键字,连续很重要,不是子序列。
题目只要求返回结果,不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。
关键 2:如何定义子问题(如何定义状态)
设计状态思路:把不确定的因素确定下来,进而把子问题定义清楚,把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题,进而把简单的问题的解组成了复杂的问题的解。
友情提示:上面这句话大家姑且这么一看,脑子里有个印象,没有那么绝对。可能不同的人看会有不同的理解。如果我以后讲解的动态规划的设计思想与这里讲解的「设计状态思路」不一样的,我会再和大家说明。如果讲解有误导的地方,还请大家指出。
我们 不知道和最大的连续子数组一定会选哪一个数,那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。
例如,示例 1 输 ...
数塔问题
数塔问题
1.onlineJ43:数塔问题
原题链接:http://oj.haizeix.com/problem/43
有一个由数字组成的三角形数塔,站在上一层的某个点,只能到达其下方左右的两个点。现在请找到一条从上到下的路径,使得路径上所有数字相加之和最大
1.递推法从上向下求和
由数塔中到达任意一点的数字和sum = 左上方数字和suml or 右上方数字和sumr + 该数字数值num
知到达该点最大和为ans[x][y] = max(ans[x - 1][y - 1], ans[x - 1][y]) + num[x][y]==关键==
遍历最后一行,找出最大的数字即为结果
12345678910111213141516171819202122232425262728#include<iostream>#include<cstdio>using namespace std;int n;int num[1005][1005];int main(){ scanf("%d", &n); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ scanf("%d", &num[i][j]); } } //1.从两个方向取数值大的方向max(num[i - 1][j - 1], num[i - 1][j]); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ num[i][j] += max(num[i - 1][j - 1], num[i - 1][j]); } } int ans = 0; //2.遍历最后一行,找出最大的数字即为结果 for(int i = 1; i <= n; ++i){ ans = max(a ...
Lattice paths
Lattice paths
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
1.递推法递推法:dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
网格中到达任意一点的路径方案数 = 正上方方案数 + 正下方方案数:dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
递推边界为左上角点(1,1),结果为右下角点坐标(4,4)
定义循环(i, j)需要从点(1, 1)点开始
这样外边界有一圈保护0,不需要判断边界、不用考虑数组越界问题(数字0不会影响答案)
12345678910111213141516171819#include<iostream>using namespace std;long long ans[25][25];int main(){ for(int i = 1; i <= 21; ++i){ for(int j = 1; j <= 21; ++j){ //初始化左上角点的值为(1, 1) if(i == 1 && j == 1){ ans[i][j] = 1; continue; } ans[i][j] = ans[i - 1][j] + ans[i][j - 1]; } } cout << ans[21][21] << endl; return 0;}
2.组合问题123456789101112#include<iostream>using namespac ...