快乐打卡
设精力为v数组  所获得的快乐为w数组
设dp[i][j]为前i道题目 当前精力为j能获得的最大快乐值
以第i道题目选与不选作为状态划分
如果第i道题目不选 花费精力不变 仍为前i-1道题目所花费的精力值 所获得的快乐指数也不变 
    即dp[i][j]=dp[i-1][j]
如果第i道题目选 精力变为当前精力减去该道题目花费的精力值 即j-v[i]
 获得的快乐为没选这道题目所获得的最大快乐值+该道题目的快乐值
    即dp[i][j]=dp[i-1][j-v[i]]+w[i];
    所获得的最大快乐值为两种情况取max
代码实现

#include <iostream>
using namespace std;
int dp[55][2100];
int v[55],w[55];//最多50道题 精力最大为2000
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];//快乐值
    for(int i=1;i<=n;i++) cin>>v[i];//精力
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=2000;j++)
        {
            dp[i][j]=dp[i-1][j];//先假设第i道题不做
            if(j>v[i])//如果所剩精力够做这道题
            dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);//两种情况取max
        }
    }
    cout<<dp[n][2000]+1;//根据状态定义 答案为前n道题目中初始精力值为2000所能获得的最大快乐值
    初始快乐值为1 答案加1
}

一维优化：
由于dp[i][j]转移方程用到的是dp[i-1][x]转移过来的状态
所以我们只要保证枚举顺序j从大到小 dp[i][j]就会用到上一层i-1的某个j转移过来的状态
此时dp[j]表示当前精力为j所能获得的最大快乐值
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e3+10;
int v[N],w[N],dp[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
        for(int i=1;i<=n;i++) cin>>v[i];    
    for(int i=1;i<=n;i++)
    {
        for(int j=2000;j>=v[i];j--)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    cout<<dp[2000]+1;
}


/*设dp[i][j]为第一个字符串前i个字符与第二个字符串前j个字符的最大公共子序列数
以第i个字符和第j个字符是否相等作状态划分
如果相等 前i个字符和前j个字符的最大子序列数为
第一个字符串的前i-1个字符和第二个字符串的前j-1个字符的最大匹配数加上当前匹配成功的一个
即dp[i][j]=dp[i-1][j-1]+1
如果不相等 dp[i][j]从前面的状态转移
可以取第一个字符串的前i-1个字符和第二个字符串的前j个字符的最大公共子序列数
也可以取第一个字符串的前i个字符和第二个字符串的前j-1个字符的最大公共子序列数
dp[i][j]为两者的max*/


#include <iostream>
using namespace std;
const int N=1010;
int dp[N][N];
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    s1=' '+s1; s2=' '+s2;//dp枚举下标从一开始 防止i-1时数组越界
    for(int i=1;i<s1.size();i++)
    {
        for(int j=1;j<s2.size();j++)
        {
            if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[s1.size()-1][s2.size()-1];
}