转载本文请联系Java极客技术公众号。大家好，我是阿芬。之前有一篇文章给大家介绍动态规划，通过两个案例给大家演示一下。后台的很多小伙伴也提出了很多建议。没看过的可以去看whatisdynamicprogramming——从青蛙跳的步骤开始理解。今天再给大家介绍两个案例，帮助大家更好的掌握，顺便复习一下。案例一问题：给定一个包含非负整数的mxn格子，请找出一条从左上角到右下角的路径，使得路径上的数之和最小，其中arr[m][n]表示具体值。您一次只能向下或向右移动一步。本题是上一篇案例的进阶版。思考根据上一篇文章提供的思路，我们依次进行相关步骤：定义变量：我们定义从左上角到位置(i,j)时，最小路径和为dp[i-][j-1]。那么，dp[m-1][n-1]就是我们想要的答案；寻找关系：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+arr[i][j];arr[i][j]表示格子中的值，到当前格子的最小路径等于左边或上边较小的路径加上格子本身的值；定义初始值：dp[i][0]=dp[i-1][0]+arr[i][0];,dp[0][i]=dp[0][i-1]+arr[0][i];;在第一行或第一列，累加了整行整列的值。上面对编码的分析可想而知，接下来我们就需要用代码来实现了。对于之前需要用到的记录，我们可以考虑使用二维数组来记录，于是有了如下代码。publicintdp(int[][]arr){intm=arr.length;intn=arr[0].length;if(m<=0||n<=0){return0;}int[][]dp=newint[m][n];//初始化dp[0][0]=arr[0][0];//初始化最左边一列for(inti=1;i
