“王子开始在左上角，每次只能往左或往右走一步，由于魔王布了陷阱，每走一步都会失去部分生命值”
“王子有初始生命，请问王子能否成功救出公主”？
“这案例就没法用排列组合来做了，应为不是每个格子都是一样的数字了。”八哥不紧不慢的举了个例子。
“好像是诶，排列组合有点难，感觉动态规划挺好做的吧”罗拉想了一会，还是放弃用排列组合了。
“是的，你可以试试动态规划怎么做呗。”
“嗯，我看看，也做了好多题了，看看能不能独立做出来，你别给我提示了，我先理一下” 看来罗拉干劲十足啊。
“王子有初始血量，想要成功就出公主就不能半路给跪了”
“要救出公主，只要我失去的生命值小于初始生命值，就可以了”
“只要求出所有路径算损失生命值的最小值和王子初始生命值做对比，就可以知道王子有没有可能救出公主了”
“所以这个也是一个求最小值得问题”
罗拉显然思路很清晰
“接下来就是分析一下动态规划要怎么做了”
“用dp[x][y]记录走到(x,y)时损失的生命值”
“由于只能向左或向右，所以相关的子问题为dp[x][y]=dp[x-1][y]+dp[x][y-1]”
“接下来考虑边界问题”
“向右只有一条路经，所以dp[x][0]=dp[x-1][0]+(x,0)”
“向下也只有一条路dp[0][y]=dp[0][y-1]+(0,y)”
“入口，也就是(0,0)应该不损失生命值，所以，dp[0][0]=0”
“然后就是编写代码了”
“完事，你看看”罗拉用力敲下最后一下键盘。
public class SavePrincess { //魔王宫殿 static int palaces[][] = { {0, 6, 9, 10, 12, 15}, {17, 33, 32, 8, 21, 20}, {3, 44, 11, 20, 1, 0}}; public static void main(String[] args) { int init = 50;//初始生命值 int min = save(); System.out.println("王子初始血量为:" + init + "， " + (min - init >= 0 ? "不能" : "能") + "救出公主"); init = 80;//初始生命值 System.out.println("王子初始血量为:" + init + "， " + (min - init >= 0 ? "不能" : "能") + "救出公主"); System.out.println("就出公主的损失生命值得最小值为:" + min); } /** * 拯救公主的最低损失生命值 * @return */ public static int save() { int n = palaces.length; int m = palaces[0].length; int[][] dp = new int[n][m]; //起始位置为0 dp[0][0] = 0; //向下初始化 for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + palaces[i][0]; //向右初始化 for (int i = 1; i < m; i++) dp[0][i] = dp[0][i - 1] + palaces[0][i]; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + palaces[i][j]; } } return dp[n - 1][m - 1]; } } //输出结果 王子初始血量为:50， 不能救出公主 王子初始血量为:80， 能救出公主 就出公主的损失生命值得最小值为:54“嗯，不错，看来动态规划你掌握的不错了。”八哥看了看结果，点头笑道。
“做多了几道题，感觉就这么回事，没啥难度。”罗拉不免翘起了尾巴。
“别开心的太早，明天我找个经典案例给你试试？”八哥不怀好意道
“没问题，今晚出去吃吧，难得这么早下班。”
“好啊，等下，我先把宝贝放好先”。