acwing897. 最长公共子序列

leetcode53. 最大子数组和

分析用f[i]来表示数组中第i个位置的最大数组和，那么计算f[i]的时候就需要从f[i-1]转移过来，转移方程为f[i]=max(f[i-1]+nums[i],nums[i]),由于只与f[i]和f[i-1]有关，可以用pre来表示i-1,ans来表示i。class Solution {public

acwing896. 最长上升子序列 II

acwing895. 最长上升子序列

acwing875. 快速幂

acwing898. 数字三角形

acwing9. 分组背包问题

分析01背包是每个物品只能选一次，这里是每组只能选一个，我们可以遍历s[i]次。选出每组中的最大值即可。#include<iostream>using namespace std;const int N=110;int v[N][N],w[N][N],s[N],f[N];int n,m;

acwing5. 多重背包问题 II(二进制优化）

分析如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。那么根据数据范围，这样的时间复杂度是O(n^3),也就是1e+9，这样是毫无疑问是会TLE的思路一个10进制数字可以由二进制数表示，我们把每一种物品都按二进制分堆，并计算每个堆的体积和价值，这样每个堆就是只能使用一次，就变成了

acwing4. 多重背包问题 I

acwing3. 完全背包问题