nbufxz动态规划1

草药题

dp[i][j]，考虑i个草药，j个时间，能获得的最大价值。这i个草药中，你不一定全部都采集了。你可能有的采了，有的没采。然后你最终得到了一个最优的结果。

状态转移方程无非就是：

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

因为你其实就是在考虑了i-1个草药的基础上，再去考虑第i个草药，所以你面对的只有两个情况，采或者不采。因为我们要的是那个数值最大化，对吧，dp承载的也就是一个数值。

dp真的好神奇，遵循我给的规则，就可以推导出最优解的宇宙...

区间dp更是难懂

    // 为什么只找一个分割点k就可以保证最优解了？
    // 1. 我们把ij看成一段，找到k之后拆成两段。对于这两段中的任意一段，也是同样的处理！
    // 2. 我们考虑了所有合法的分割方式！
    // 3. 每个子区间的最优值是我事先用dp算出来的（从l=2开始）

#include<iostream>
using namespace std;#define MAX_N 100
int a[MAX_N + 1];
int n;
int dp[MAX_N + 1][MAX_N + 1];
// dp[i][j]表示区间ij爆炸的最小能量int main() {cin >> n;for (int i = 0; i <= n; i++) {cin >> a[i] ;}// dp初始化，一个珠子爆炸是没能量的for (int i = 0; i <= n; i++) {dp[i][i] = 0;}for (int l = 2; l < n; l++) {for (int i = 1; i <= n; i++) {// 区间起点iint j = i + l - 1; // 区间终点jdp[i][j] = INT_MAX;for (int k = i; k < j; k++) { // 为什么k不等于j你懂的dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j]);}}}// 为什么只找一个分割点k就可以保证最优解了？// 1. 我们把ij看成一段，找到k之后拆成两段。对于这两段中的任意一段，也是同样的处理！// 2. 我们考虑了所有合法的分割方式！// 3. 每个子区间的最优值是我事先用dp算出来的（从l=2开始）printf("%d\n", dp[1][n]);return 0;
}

嘿嘿嘿自己写了一道完整的dp题~

有个小细节最开始错了，下面的行，i应该+1而不是-1...抽风了

#include<iostream>
using namespace std;#define MAX_N 105
int t[MAX_N][MAX_N];
int n;
int dp[MAX_N][MAX_N];
// dp[i][j]表示t[i][j]的数到达底层的最大值int main() {cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> t[i][j];}}// 初始化一下for (int i = 1; i <= n; i++) {dp[n][i] = t[n][i];}// 从下往上dp慢慢推for (int i = n - 1; i >= 1; i--) {for (int j = 1; j <= i; j++) {dp[i][j] = max(dp[i + 1][j] + t[i][j],dp[i + 1][j + 1] + t[i][j]// 最开始弱智写成i - 1了);}}cout << dp[1][1];return 0;
}