引言

在算法的世界中，动态规划是一种强大的方法，用于解决具有重叠子问题和最优子结构的问题。它从记忆化搜索发展而来，但提供了一种更为系统和强大的解决方案。

记忆化搜索

记忆化搜索是一种优化递归算法的技术，通过存储已解决子问题的解来避免重复计算。这种方法在解决组合优化问题时非常有用，如整数规划问题。

动态规划

动态规划通常自底向上地构建解决方案，从最小的子问题开始，逐步构建到原始问题的解。它通常使用表格来存储中间结果，从而避免重复计算。

背包问题

背包问题是动态规划的经典应用之一，包括01背包、完全背包和多重背包问题。每种背包问题都有其特定的动态规划模型：

1. 01背包问题：每种物品只能选取一次或不选取。状态转移方程为 dp[j] = max(dp[j], dp[j - w[i]] + v[i])，其中 w[i] 和 v[i] 分别是物品的重量和价值。

2. 完全背包问题：每种物品可以选取多次。状态转移方程与01背包类似，但需要考虑物品数量上限。

3. 多重背包问题：每种物品有数量限制。状态转移方程需要考虑数量限制。

经典模型：LIS和LCS

LIS（Longest Increasing Subsequence）和LCS（Longest Common Subsequence）是动态规划中的两个经典模型，用于解决最长递增子序列和最长公共子序列问题。

• LIS问题：给定一个序列，找到最长的严格递增子序列。

• LCS问题：给定两个序列，找到最长的公共子序列。

这些问题可以通过动态规划方法解决，通过构建状态转移方程来找到最优解。

题目分析：

1.最大子段和

该问题可直接从头到尾便利，计算所有大于0的字段和，并且实时更新最大字段和最后输出答案。

AC代码如下：

#include<iostream>
using namespace std;
int main() {
    int n,a;
    int max=0,ans=-10000;
    cin >> n;
    while (n--) {
        cin >> a;
        max = max + a; 
        if (ans < max)ans = max;
        if (max < 0)max = 0;
    }
    cout << ans;
    return 0;
}

2.采药

该题是01背包问题，可用二维01背包直接计算。

其中，状态转移方程为dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]]+w[i])。

AC代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;
int main(){
int T,M,t[N],w[N];
cin>>T>>M;
for(int i=1;i<=M;i++){
cin>>t[i]>>w[i];
}
int dp[N][N]={0};
for(int i=1;i<=M;i++){
for(int j=0;j<=T;j++){
dp[i][j]=dp[i-1][j];
if(j>=t[i])dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]]+w[i]);
}
}
cout<<dp[M][T];
return 0;
}

3.宝物筛选

该题为多重背包问题，可以先转化成01背包。

直接转化的话会超时，可以使用二进制转化。

将每一种宝物都拆分成1，2，4，8...2^(k-1),n-2^k+1个, 随后使用一维01背包计算。

#include<iostream>
#include<algorithm>
using namespace std;
int f[100005];
int main()
{
    int n,W;
    cin>>n>>W;
    for(int i=1;i<=n;i++)
    {
        int v,w,m;
        cin>>v>>w>>m;
        for(int k=1;k<=m;k*=2)//可以二进制的数
        {
            for(int j=W;j>=k*w;j--)
            {
                f[j]=max(f[j],f[j-k*w]+k*v);
            }
            m-=k;
        }
        for(int j=W;j>=m*w;j--)//余下来的数
        {
            f[j]=max(f[j],f[j-m*w]+m*v);
        }
    }
    cout<<f[W];
    return 0;
}

4.最长公共子序列

该问题可以转变两数组值与值的联系，改为值与位置的联系，转换为最长上升子序列问题。利用二分的优势快速求解。

AC代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
const int ma=0x7fffffff;
int n,len=1;
int a[N],b[N],dp[N],mp[N];
int main(){
    fill(dp,dp+N,ma);
    dp[0]=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]=i;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        if(mp[b[i]]>dp[len])dp[++len]=mp[b[i]];//大的直接添加
        else dp[lower_bound(dp,dp+len,mp[b[i]])-dp]=mp[b[i]];//小的二分查找替换
    }
    cout<<len<<endl;
    return 0;
}

5.Kevin and Puzzle

通过观察，我们发现了以下性质

1.如果第 i 个人说谎，那么第i- 1个人和i+1个人都说真话，数值差1

2.如果第 i 个人和第 i − 1 个人说的都是真话，那么他们位置上的数字相等。

f[i][0\1]分别表示第i个人说谎、说真话的方案数

若第i个人说谎f[i][0]=f[i-1][1];

若第i-1个人说真话f[i][1]+=f[i-1][1];

若第i-1个人说谎话f[i][1]+=f[i-1][0];

初始化状态，如果第一个人的数字为零，则他有可能说真话，否则一定说假话。

AC代码如下：

#include<iostream>

using namespace std;

const int N=200005,p=998244353;

int t,n,a[N],f[N][2];

int main(){

 cin>>t;

 while(t--){

  cin>>n;

  for(int i=1;i<=n;i++){

   cin>>a[i];

   f[i][0]=0;f[i][1]=0;

  }

  f[1][0]=1;

  if(a[1]==0) f[1][1]=1;

  else f[1][1]=0;

  for(int i=2;i<=n;i++){

   f[i][0]=f[i-1][1];

   if(a[i]==a[i-1]){

    f[i][1]+=f[i-1][1];

    f[i][1]%=p;

   }

   if(a[i]==a[i-2]+1){

    f[i][1]+=f[i-1][0];

    f[i][1]%=p;

   }

  }

  int ans=(f[n][1]+f[n][0])%p;

  cout<<ans<<endl;

 }

 return 0;

}

6.World is Mine

可以发现，A在整场游戏中的行为是固定的，每一次都只选择美味值最小的蛋糕。问题的关键就是在于B每一次要选取适当的蛋糕使自身占优势。由于A每一种蛋糕只能吃一个，所以B要清除掉同一种类的所有蛋糕。

将每种蛋糕的数量依据蛋糕的口味由低到高排序记录。B的背包空间就相当于A进行游戏的次数，最后遍历dp数组，找到B最大可以清零的蛋糕种类，其余种类A各吃一个，即答案。

AC代码如下：

#include <iostream>

#include<algorithm>

#include<cstring>

#include<vector>

using namespace std;

const int N = 5050;

int a[N];

int dp[N];

int main ()

{

    ios::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    int t,n; 

    cin >>t;

    while(t--){

    memset(a,0,sizeof(a));

    memset(dp,0,sizeof(dp));

    cin >> n;

    vector<int> v;

    for(int i=1; i<=n;i++){

        int x; cin >>x;

        a[x]++;

    }

    for(int i=1;i<=5000;i++)

        if(a[i]) v.push_back(a[i]);

    int m = v.size();

    for(int i=1 ;i<m;i++){

        for(int j=i;j>=0;j--){

            if(j >=v[i]) {

                dp[j+1] = max(dp[j-v[i]]+1, dp[j+1]);

            }

        }

    }

    int mx =0;

    for(int i=0;i<=m;i++){

        mx = max(mx,dp[i]);

    }

    cout<<m-mx<<endl;

    }

    return 0;

}

结语

动态规划是解决复杂优化问题的强大工具，它从记忆化搜索发展而来，提供了一种更为系统化的解决方案。通过理解动态规划的基本概念和应用，我们可以更有效地解决实际问题，如背包问题和序列问题。