区间DP - 石子合并

const int N = 310, INF = 0x3f3f3f3f;
int n, m[N], s[N], dp[N][N];
int main()
{cin >> n;for(int i = 1; i <= n; ++i){cin >> m[i];s[i + 1] = s[i] + m[i];}fill(dp[0], dp[0] + N * N, INF);            // 初始化为正无穷以避免干扰状态计算for(int i = n; i >= 1; --i){for(int j = i; j <= n; ++j){if(i == j)                          // 单独堆石子的合并代价为0dp[i][j] = 0;                   else                                // 注意合并代价的累加，{                                   // 这里以最后一步研究，最后一次合并的代价是区间内的质量和for(int k = i; k < j; ++k)      // 区间质量和通过前缀和直接获得dp[i][j] = min(dp[i][k] + dp[k + 1][j] + s[j + 1] - s[i], dp[i][j]);}// printf("dp[%d][%d]:%d\n", i, j, dp[i][j]);// cout << dp[i][j] << " ";}}cout << dp[1][n];return 0;
}

背包应用 - 整数划分

const int N = 1010, MOD = 1e9 + 7;
int n, dp[N][N];
int main()
{cin >> n;for(int i = 0; i <= n; ++i)dp[i][0] = 1;for(int i = 1; i <= n; ++i){for(int j = 0; j <= n; ++j)         // 注意此段的细节处理{dp[i][j] = dp[i - 1][j] % MOD;  // 先加上不选i的选法if(j >= i)                      // 在j>=i的情况下，累加上选k个i的选法数dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % MOD;}}cout << dp[n][n];return 0;
}