一、爬楼梯
爬楼梯
class Solution {
public:int climbStairs(int n) {int p = 1;int q = 2;if (n == p)return p;else if (n == q)return q;else {int r;for (int i = 3; i <= n; i++) {r = p + q;p = q;q = r;}return r;}}
};复杂度分析
- 时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
- 空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。
二、杨辉三角
杨辉三角
class Solution {
public:vector<vector<int>> generate(int numRows) {if (numRows == 0) return {}; // 处理 0 行的情况vector<vector<int>> ans; for (int i = 0; i < numRows; i++) {vector<int> oneans(i + 1, 1); // 每次都直接初始化当前行for (int j = 1; j < i; j++) { // 计算中间部分oneans[j] = ans[i - 1][j - 1] + ans[i - 1][j];}ans.emplace_back(oneans); // 存入结果}return ans;}
};
三、打家劫舍
打家劫舍
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();int f1 = nums[0];int ans = f1;if (n == 1)return nums[0];int f0 = 0;int newf = 0;for (int i = 2; i <= nums.size(); i++) {newf = max(f0 + nums[i - 1], f1);f0 = f1;f1 = newf;}return newf;}
};思路：偷：newf = 上上个状态+nums[i]；不偷： newf = 上个状态。
四、01背包问题
01背包问题
二维版本：
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, m;
int dp[N][N];
int v[N], w[N];int main(){cin >> n >> m;for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){dp[i][j] = dp[i - 1][j];if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}cout << dp[n][m];return 0;
}作者：断然
链接：https://www.acwing.com/solution/content/116859/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。一维版本：
题解参考：降维题解
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, m;
int dp[N];
int v[N], w[N];int main(){cin >> n >> m;for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];for (int i = 1; i <= n; i++)for (int j = m; j >= v[i]; j --)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << dp[m];return 0;
}作者：断然
链接：https://www.acwing.com/solution/content/116859/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。五、完全背包问题
完全背包问题
暴力版：
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++)for(int j = 0 ; j<=m ;j++){for(int k = 0 ; k*v[i]<=j ; k++)f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}cout<<f[n][m]<<endl;
}作者：Charles__
链接：https://www.acwing.com/solution/content/5345/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。优化版：
参考 优化题解
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{f[i][j] = f[i-1][j];if(j-v[i]>=0)f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);对比01背包的非优化写法
for(int i = 1 ; i <= n ; i++)
for(int j = 0 ; j <= m ; j ++)
{f[i][j] = f[i-1][j];if(j-v[i]>=0)f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
这里为什么可以从小到大枚举？就是因为二者递归方程的重要不同，01背包要用上一次的，而完全背包必须用更新过后的，正好j严格大于j-v[i]，所以正好更新过了。
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++)for(int j = v[i] ; j<=m ;j++){f[j] = max(f[j],f[j-v[i]]+w[i]);}cout<<f[m]<<endl;
}作者：Charles__
链接：https://www.acwing.com/solution/content/5345/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
