二维动规思想, j 没有明显枚举特征

题目

1. POJ Balance
2. 九度 出入栈
3. POJ Communication System
4. Find the multiple

 思路

1. 共性: dp[i][j] 中第二个变量 j 并不明确.

2.第一题. dp[i][j] 表示放入第 i 个秤砣后平衡系数为 j 的方案数

j 的范围位置, 因此使用 PUSH 更好

dp[i][j+weight[i]*dist] += dp[i][v]

3. 第二题 出入栈

dp[i][j] 表示前 i 个操作序列中入栈操作个数为 j 的方案数

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 枚举最后一位是入栈还是出栈

4. 第三题 交流系统.

dp[i][j] 表示前 i 件设备带宽为 j 时的最小花费

dp[i][j] = min(dp[i-1][k]+cost[j])