动态规划一>下降路径最小和
1.题目:
2.解析:
代码:
/** 1.创建dp表 2.初始化 3.填表 4.返回值 */ public int minFallingPathSum(int[][] matrix) { int n = matrix.length; int[][] dp = new int[n+1][n+2]; int minNum = Integer.MAX_VALUE; for(int i = 1; i <= n; i++) dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1])) + matrix[i-1][j-1]; for(int i = 1; i <= n; i++) minNum = Math.min(minNum,dp[n][i]); return minNum; }