[数据结构与算法]DP练习day1

luogu P1802 5倍经验日

题目链接
难度：普及-

一. 思路：

这道题是非常基础的题。

重叠子问题、最优子结构、无后效性、状态转移方程是动态规划核心要素。如何合理分解出重叠的、具有最优子结构、无后效性的子问题，确定状态，写出状态转移方程是核心难点。

1. “状态”的初步确定

“状态”也就是原问题和子问题中会变化的变量。“状态"下的“值”，就是这个“状态”所对应的问题的解。“状态”的变化导致“值”的变化。“状态”的确定和“子问题”的分解方式是相互关联的，这里我们先初步确定“状态”，再分析子问题分解。

本题中显然“状态”是好友数n和药量x，“状态”下的值是经验值。

2. 子问题分解

本题分解子问题的思路非常典型，和子序列问题是相同的。分解子问题时要满足无后效性、重叠性、最优子结构。

本题非常典型的错误就是没有对所有状态变量同时考虑，导致不满足无后效性。如将子问题直接分解为“求挑战前i个好友的最大经验值”，这样就忽略了另一个状态药量x，进而不满足无后效性。

在分析时，我们可以充分利用递归的思路，即将前n-1步看作整体性的黑盒，只讨论第n步所独有的已知状态。那么我们能利用的已知数据除了前n-1步的值，就只有挑战第n个好友获得的经验、所需药量。而对于经验是要分类讨论，因而子问题即“战胜第n个好友后，前n步能获得的最大经验值”和“输给第n个好友后，前n步能获得的最大经验值”。这个问题显然满足三个性质要求。需要注意的是两种子问题的是否成立取决于药量x的多少，还要对此进行讨论。

从图像的角度理解，递归可以用树来表示，而动归的存储过程就可以理解为“剪枝”的过程。在子问题分解时，我们实际就是在为根节点规定孩子节点。

3. 状态转移方程的确定：

$$dp[n][x]=?\begin{array}{l}dp[n?1][x]+lose[n],x<num[n]\\ \\ max(dp[n?1][x]+lose[n],dp[n?1][x?num[n]]+win[n]),x>=num[n]\end{array}$$

4. 化递归为递推

递推是从已知量来推导未知量。递推式可以借助状态的表格进行辅助分析

对于最简单的题目，递推式只需要从一个量推它相邻的几个量。而像本题这种，推导过程是在表格上跳跃的，但我们能确定的是要求的dp[n][x], dp[n-1]上所有列的数值都必须先要被确定。因而我们for循环遍历时只需先遍历n,在遍历x即可。

二. 代码：

记忆递归型：

#include <bits/stdc++.h>
#define LEN 1001
using namespace std;
int data[LEN][3];
long res[LEN][LEN]={0};
//记忆递归型
int jingyan(int n,int x){
    if  (n==0)
        return 0;
    else
    {
        if (res[n][x]==0)
        {
            if (x>=data[n][2])
                res[n][x] = max(jingyan(n - 1, x) + data[n][0], 
                    jingyan(n - 1, x - data[n][2]) + data[n][1]);
            else
                res[n][x] = jingyan(n - 1, x) + data[n][0];
        }
    }  
    return res[n][x];  
}
int main(){
    int n,x;
    while(cin >> n >> x)
    {
        for (int i = 1; i <= n;i++)
            cin >> data[i][0] >> data[i][1] >> data[i][2];
        cout << 5*jingyan(n, x)<<endl;
    }
    return 0;
}

“人人为我”递推

#include <bits/stdc++.h>
#define LEN 1001
int data[LEN][3];
long res[LEN][LEN]={0};
int main(){
    using namespace std;
    int n, x;
    while(cin >> n >> x)
    {
        for (int i = 1; i <= n;i++)
            cin >> data[i][0] >> data[i][1] >> data[i][2];

        for (int i = 1; i <= n;i++)
            for (int j = 0; j <= x;j++)//for(int j=x;j>=0;j--)
                if(j>=data[i][2])
                    res[i][j] = max(res[i - 1][j] + data[i][0],
                                    res[i - 1][j - data[i][2]] + data[i][1]);
                else 
                    res[i][j] = res[i - 1][j] + data[i][0];
        cout << 5 * res[n][x] << endl;
    }
}

“我为人人”递推

#include <bits/stdc++.h>
#define LEN 1001
int data[LEN][3];
long res[LEN][LEN]={0};
int main(){
    using namespace std;
    int n, x;
    while(cin >> n >> x)
    {
        for (int i = 1; i <= n;i++)
            cin >> data[i][0] >> data[i][1] >> data[i][2];

        for (int i = 0; i < n;i++)
            for (int j = 0; j <= x;j++)
                if(j>=data[i+1][2])
                    res[i+1][j] = max(res[i][j] + data[i+1][0],
                                    res[i][j - data[i+1][2]] + data[i+1][1]);
                else 
                    res[i+1][j] = res[i][j] + data[i+1][0];
        cout << 5 * res[n][x] << endl;
    }
}

三. 其他反思

初值确定时，既要考虑全面，也不要啰嗦太多、画蛇添足。

注意题目数据大小的存储限制。