跳台阶
一个楼梯共有 nn 级台阶，每次可以走一级或者两级，问从第 00 级台阶走到第 nn 级台阶一共有多少种方案。
输入格式
共一行，包含一个整数 nn。
输出格式
共一行，包含一个整数，表示方案数。
数据范围
1≤n≤151≤n≤15
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int temp1=1, temp2=2, newF=0;
for(int i=3; i<=n; i++){
newF=temp1+temp2;
temp1=temp2;
temp2=newF;
}
cout<<newF;
return 0;
}
|
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int dfs(int x){
if(mem[x]) return mem[x];
int sum=0;
if(x==1) sum=1;
else if(x==2) sum=2;
else sum = dfs(x-1)+dfs(x-2);
mem[x]=sum;
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int res=dfs(n);
cout<<res;
return 0;
}
|
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
|
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
|
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
#include<bits/stdc++.h>
using namespace std;
const int N=120;
int home[N];
int main(){
int T, n;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &home[i]);
}
int newf=0, tmp1=0, tmp2=0;
for(int i=1; i<=n; i++){
newf=max(tmp1, tmp2+home[i]);
tmp2=tmp1;
tmp1=newf;
}
printf("%d\n", newf);
}
return 0;
}
|
数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。
输入格式
第一个行一个正整数 r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
输入输出样例
输入 #1复制
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
|
输出 #1复制
说明/提示
【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int g[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
cin>>g[i][j];
}
}
for(int i=n; i>=1; i--){
for(int j=1; j<=i; j++){
f[i][j]=max(f[i+1][j], f[i+1][j+1])+g[i][j];
}
}
printf("%d", f[1][1]);
return 0;
}
|
背包问题
有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000
输入样例
输出样例：
直接写dfs
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, m;
int v[N], w[N];
int dfs(int x, int spV){
if(x>n) return 0;
else if(spV < v[x]){
return dfs(x+1, spV);
}
else if(spV>=v[x]){
return max(dfs(x+1, spV), dfs(x+1, spV-v[x])+w[x]);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>v[i]>>w[i];
}
int res=dfs(1, m);
cout<<res<<endl;
return 0;
}
|
优化
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, m;
int v[N], w[N];
int mem[N][N];
int dfs(int x, int spV){
if(mem[x][spV]) return mem[x][spV];
int sum=0;
if(x>n) sum=0;
else if(spV < v[x]){
sum=dfs(x+1, spV);
}
else if(spV>=v[x]){
sum=max(dfs(x+1, spV), dfs(x+1, spV-v[x])+w[x]);
}
mem[x][spV]=sum;
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>v[i]>>w[i];
}
int res=dfs(1, m);
cout<<res<<endl;
return 0;
}
|
递推
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>v[i]>>w[i];
}
for(int i=n; i>=1; i--){
for(int j=0; j<=m; j++){
if(j<v[i]){
f[i][j]=f[i+1][j];
}
else if(j>=v[i]){
f[i][j]=max(f[i+1][j], f[i+1][j-v[i]]+w[i]);
}
}
}
cout<<f[1][m];
return 0;
}
|
二维费用的背包问题
有 NN 件物品和一个容量是 VV 的背包，背包能承受的最大重量是 MM。
每件物品只能用一次。体积是 vivi，重量是 mimi，价值是 wiwi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式
第一行三个整数，N,V,MN,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 NN 行，每行三个整数 vi,mi,wivi,mi,wi，用空格隔开，分别表示第 ii 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤10000<N≤1000
0<V,M≤1000<V,M≤100
0<vi,mi≤1000<vi,mi≤100
0<wi≤10000<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
|
输出样例：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V, M;
int v[N], m[N], w[N];
int mem[N][110][110];
int dfs(int x, int spV, int spW){
if(mem[x][spV][spW]) return mem[x][spV][spW];
int sum=0;
if(x>n) sum=0;
else if(v[x]>spV || m[x]>spW){
sum=dfs(x+1, spV, spW);
}else{
sum=max(dfs(x+1, spV, spW), dfs(x+1, spV-v[x], spW-m[x])+w[x]);
}
mem[x][spV][spW]=sum;
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>V>>M;
for(int i=1; i<=n; i++){
cin>>v[i]>>m[i]>>w[i];
}
int res=dfs(1, V, M);
cout<<res<<endl;
return 0;
}
|
递推
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V, M;
int v[N], m[N], w[N];
int f[N][110][110];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>V>>M;
for(int i=1; i<=n; i++){
cin>>v[i]>>m[i]>>w[i];
}
for(int i=n; i>=1; i--){
for(int j=0; j<=V; j++){
for(int k=0; k<=M; k++){
if(j<v[i]||k<m[i]){
f[i][j][k]=f[i+1][j][k];
}else{
f[i][j][k]=max(f[i+1][j][k], f[i+1][j-v[i]][k-m[i]]+w[i]);
}
}
}
}
cout<<f[1][V][M]<<endl;
return 0;
}
|
完全背包问题
有 NN 种物品和一个容量是 VV 的背包，每种物品都有无限件可用。
第 ii 种物品的体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000
输入样例
输出样例：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V;
int v[N], w[N];
int mem[N][N];
int dfs(int x, int spV){
if(mem[x][spV]) return mem[x][spV];
int sum=0;
if(x>n) sum=0;
else if(spV<v[x]){
sum=dfs(x+1, spV);
}
else if(spV>=v[x]){
sum=max(dfs(x+1, spV), dfs(x, spV-v[x])+w[x]);
}
mem[x][spV]=sum;
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>V;
for(int i=1; i<=n; i++){
cin>>v[i]>>w[i];
}
int res=dfs(1,V);
cout<<res<<endl;
return 0;
}
|
递推
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V;
int v[N], w[N];
int f[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>V;
for(int i=1; i<=n; i++){
cin>>v[i]>>w[i];
}
for(int i=n; i>=1; i--){
for(int j=0; j<=V; j++){
if(j<v[i]){
f[i][j]=f[i+1][j];
}else if(j>=v[i]){
f[i][j]=max(f[i+1][j], f[i][j-v[i]]+w[i]);
}
}
}
cout<<f[1][V]<<endl;
return 0;
}
|
使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
|
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
|
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
递归
class Solution {
public:
int dfs(vector<int>& cost, int x){
if(x==0 || x==1) return 0;
else{
return min(dfs(cost, x-1)+cost[x-1], dfs(cost, x-2)+cost[x-2]);
}
}
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
int ans=dfs(cost, n);
return ans;
}
};
|
记忆化
const int N=1010;
class Solution {
public:
int mem[N];
int dfs(vector<int>& cost, int x){
if(mem[x]) return mem[x];
int sum=0;
if(x==0 || x==1) sum=0;
else{
sum=min(dfs(cost, x-1)+cost[x-1], dfs(cost, x-2)+cost[x-2]);
}
mem[x]=sum;
return sum;
}
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
int ans=dfs(cost, n);
return ans;
}
};
|
递推
const int N=1010;
class Solution {
public:
int f[N];
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
f[0]=0;
f[1]=0;
for(int i=2; i<=n; i++){
f[i]=min(f[i-1]+cost[i-1], f[i-2]+cost[i-2]);
}
return f[n];
}
};
|
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
|
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
|
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
|
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
递推
class Solution {
public:
int dfs(vector<int>& nums, int x){
int res=0;
for(int i=0; i<x; i++){
if(nums[i]<nums[x]){
res=max(res, dfs(nums, i)+1);
}
}
return res;
}
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
int res=-1e9;
for(int i=0; i<n; i++){
res=max(res, dfs(nums, i));
}
return res+1;
}
};
|
记忆化搜索
class Solution {
public:
int mem[2510];
int dfs(vector<int>& nums, int x){
if(mem[x]) return mem[x];
int res=0;
for(int i=0; i<x; i++){
if(nums[i]<nums[x]){
res=max(res, dfs(nums, i)+1);
}
}
mem[x]=res;
return res;
}
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
int res=-1e9;
for(int i=0; i<n; i++){
res=max(res, dfs(nums, i));
}
return res+1;
}
};
|
递推
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int f[2510];
int n=nums.size();
int res=-1e9;
for(int i=0; i<n; i++){
f[i]=1;
for(int j=0; j<i; j++){
if(nums[j]<nums[i]){
f[i]=max(f[i], f[j]+1);
}
}
}
for(int i=0; i<n; i++){
res=max(res, f[i]);
}
return res;
}
};
|
