本文共 1457 字，大约阅读时间需要 4 分钟。
问题A：
n个骰子和为s的概率：dp，时间O(ns6)，空间O(s)
dp计算一个长度为s+1的数组，dp[i]表示和为 i 的次数。
概率分母一定是6^n，分子即为dp[s]问题B：
中序遍历为1，2，…，n的搜索二叉树有多少种结构？
dp，时间O(N*N)
dp[i] 表示节点为i的树有多少种结构，故而，dp[0] = 1 转移方程，dp[i] = sum{ dp[j-1] * dp[i-j] }问题C：
打气球的最大分数：
数组Arr存放每个气球爆破得分，当挤爆气球时，得分规则为，当前气球得分 * 左边未爆气球得分 * 右边未爆气球得分，如何选择挤爆气球顺序使得分最大？dp[ L ][ R ]，时间O(NNN)
其中dp[L][R]表示区间[L,R]上当最大得分。动态转移方程为:
dp[L][R] = max{ dp[L][R], dp[L][k-1] + dp[k+1][R] + Arr[L-1]*Arr[k]*Arr[R+1] }动态规划表的填充顺序为：
注意到，每个dp[L][R] 只依赖 dp[L][k-1] 和 dp[k+1][R]的值，即为其左侧和下侧数据，则打表顺序为，L从左至右，R从下至上，然后枚举k。问题D：
表达式得到期望结果的组成数量： 例如，1^0|0|1，要得到false的种类dp，时间O(NNN)
t[i][j]表示区间[i…j]上表达为真的个数。
f[i][j]表示区间[i…j]上表达为假的个数。同上一道题，dp[i][j]依赖左侧和下侧元素，则自左向右，自下而上遍历。
枚举k为区间[i…j]划分点，例如遍历方式如下：for(int R = 0;R < N ; R+=2){ for(int L = R; L >= 0 ; L-=2){ for(int K = L+1; K < R ; K+=2){ }}} 问题E：
纸牌博弈 排成一列的纸牌只能从两边拿，规定A先拿，B后拿，则获胜者分数？dp，时间O(N*N)
维护两个dp表，first[i][j]代表区间[i…j]先拿的最大分数。
second[i][j] 代表区间[i…j]后拿的最大分数。转移方程：
f[i][j] = max{ Arr[i] + s[i+1][j] , Arr[j] + s[i][j-1] } 很好理解，当选了边界某一值后，就只能在剩下区间里后拿了。 s[i][j] = min{ f[i+1][j] , f[i][j-1] } 很好理解，在区间[i…j]上，对方先选当话只会给自己留下较差的情况。换一种思路，若f[i][j] 选择 Arr[i] + s[i+1][j] 后，s[i][j] 只能选f[i+1][j]了，递归可以发现，s[i][j]其实就是选min{f[i+1][j] , f[i][j-1]}。问题F：
龙与地下城游戏： 从左上角出发，每次向右或向下，初始最少血量是多少？二分初始值，时间O(NNlog{MaxNum})
dp，时间O(N*N)二分方法略。
dp方法采用逆向思维，从右下角开始考虑所需最小血量是多少。dp[i][j] 代表必须经过位置(i,j)所需的最小血量。
right = max{ dp[i][j+1] - m[i][j] , 1 }
down = max{ dp[i+1][j] - m[i][j], 1} dp[i][j] = min{ right, down}问题G：
邮局选址问题：见：
转载地址：http://ibwji.baihongyu.com/