概念 不会算法的程序员不是好程序员，动态规划更是经典算法之一，希望这篇小博客能让大家对动态规划有一个简单的入门。 短视频APP制作动态规划其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。可能未接触过动态规划的人看到就不理解了，下面用例子给大家讲讲我对动态规划的理解 1、入门题——经典爬楼梯问题 2、简单题——经典机器人路径数问题 3、提升题——最短路径问题
（1）经典爬楼梯问题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到指定的楼梯层数呢？ 输入n 输出方法数 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 要点 ：要跳到第i层，只能从第i-1层或者从i-2层跳上去 故得到关系 f[i]=f[i-1]+f[i-2] 下面是代码与解析
class Solution { public int climbStairs(int n) { if(n==1) return 1; if(n==2) return 2; int f[]=new int[n]; //定义数组，储存第i层有f[i]种方法 f[0]=1; //跳第一层有1种方法 f[1]=2; //跳第一层有2种方法 //之后利用循环与已知f[0],f[1]求之后的层数 for(int i=2;i<f.length;i++) { //要跳到第i层，只能从第i-1层或者从i-2层跳上去 故得到关系 f[i]=f[i-1]+f[i-2] //注意i应从i=2开始循环 否则数组下标会出错 f[i]=f[i-1]+f[i-2]; } return f[n-1]; } }（2）经典路径数问题 一个机器人从一个m*n网格的最左上角出发，机器人每次只能向下或向右走一步，要走到网格的最右下角共有多少中走法？ 要点：既然是m×n的一个网格，那就要用到二维数组dp[m][n],记录走到dp[i][t]位置的网格方法数，得到： dp[i][t]=dp[i-1][t]+dp[i][t-1] 下面是代码与我的分析:
class Solution { public int uniquePaths(int m, int n) { int dp[][]=new int[m][n]; for(int i=0;i<dp.length;i++) dp[i][0]=1; //走第一列只有一条路可走 for(int i=0;i<dp[0].length;i++) dp[0][i]=1;//走第一行只有一条路可走 for(int i=1;i<dp.length;i++)// 两次循环分别控制二维数组的行和列 for(int t=1;t<dp[0].len）gth;t++)//主要解析在 要点 dp[i][t]=dp[i-1][t]+dp[i][t-1]; return dp[m-1][n-1]; } }（3）、最短路径问题 给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，求到右下角的最短路径数 给定如下： 1 3 5 9 8 0 3 4 5 0 6 1 8 8 4 0 路径1,3,0,0,0,1,0是所有路径中路径和最小的，所以返回5。 要点：二维数组dp[m][n],记录走到dp[i][j]位置的最短路径，得到： dp[i][j]=dp[i-1][j]+dp[i][j-1] 下面是代码与我的分析:
class Solution { public static int shortestRoad(int arr[][]) { int dp[][]=new int [arr.length][arr[0].length]; //储存 走到到dp[i][j]网格的最短路径的和 dp[0][0]=arr[0][0]; for(int i=1;i<arr.length;i++) //思路如上题 { dp[i][0]=dp[i-1][0]+arr[i][0]; } for(int j=1;j<arr[0].length;j++) { dp[0][j]=dp[0][j-1]+arr[0][j]; } for(int i=1;i<arr.length;i++) for(int j=1;j<arr[0].length;j++) { dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+arr[i][j]; // 选取向下或向右这两条中的最短一条 +上当前网格的数 } return dp[arr.length-1][arr[0].length-1]; } }