做网站需要多长时间才能做好,网站上传到空间,wordpress wampserve,网站页面布局的目的我们现在对杨辉三角进行一些改造。每个位置的数字可以随意填写#xff0c;经过某个数字只能到达下面一层相邻的两个数字。
假设你站在第一层#xff0c;往下移动#xff0c;我们把移动到最底层所经过的所有数字之和#xff0c;定义为路径的长度。请你编程求出从最高层移动…
我们现在对杨辉三角进行一些改造。每个位置的数字可以随意填写经过某个数字只能到达下面一层相邻的两个数字。
假设你站在第一层往下移动我们把移动到最底层所经过的所有数字之和定义为路径的长度。请你编程求出从最高层移动到最底层的最短路径长度。
分析
题目的目标是到 最底层的最短路径长度 。 目标状态是到达最底层。 分阶段按照到达第0层、第1层…第m-1层分阶段。 枚举向下走的方向下一层与此相邻的两个元素 状态维度一开始我认为状态是(i),表示到达第i层。后来发现第i层不止一个元素需要到达所有元素才能知道到达第i层的最短路径。所以状态为(i,j)表示到达第i层、第j列。 暴力搜索代码如下。
public class PascaltriangleTransform {private int[][] triangle new int[][]{new int[]{5},new int[]{7,8},new int[]{2,3,4},new int[]{4,9,6,1},new int[]{2,7,9,4,5}};/*** 对于f(i,j)是有重复计算的。例如在计算f(2,1)的时候需要计算f(1,1)计算f(2,2)的时候需要计算f(1,1)和f(1,2)。f(1,1)计算了两次* return*/public int getShortestpathSum(){int m triangle.length;int n triangle[m-1].length;int minPathSum Integer.MAX_VALUE;for(int j0;jn;j){minPathSum Math.min(minPathSum,f(m-1,j));}return minPathSum;}/*** 到达第i层,第j列的最短路径和* param i*/private int f(int i, int j) {if(j0) return Integer.MAX_VALUE;//此路不同if(jtriangle[i].length) return Integer.MAX_VALUE;//此路不同if(i0){return triangle[0][0];}else{int val1 f(i-1,j);int val2 f(i-1,j-1);return Math.min(val1,val2)triangle[i][j];}}}备忘录模式
我们可以使用之前画递归树的方式发现有重复计算的子问题。 目前我不画了推理一下。对于f(i,j)是有重复计算的。例如在计算f(2,1)的时候需要计算f(1,1)计算f(2,2)的时候需要计算f(1,1)和f(1,2)。f(1,1)计算了两次。所以肯定有重复计算的子问题。使用备忘录模式。
public class PascaltriangleTransformV2 {private int[][] triangle new int[][]{new int[]{5},new int[]{7,8},new int[]{2,3,4},new int[]{4,9,6,1},new int[]{2,7,9,4,5}};public int getShortestpathSum(){int m triangle.length;int n triangle[m-1].length;int minPathSum Integer.MAX_VALUE;int[][] memo new int[m][n];for(int j0;jn;j){minPathSum Math.min(minPathSum,f(m-1,j,memo));}return minPathSum;}private int f(int i, int j,int[][] memo) {if(j0) return Integer.MAX_VALUE;//此路不同if(jtriangle[i].length) return Integer.MAX_VALUE;//此路不同if(i0){return triangle[0][0];}else{if(memo[i][j]0) return memo[i][j];//假设triangle的值都是正整数int val1 f(i-1,j,memo);int val2 f(i-1,j-1,memo);memo[i][j] Math.min(val1,val2)triangle[i][j];return memo[i][j];}}
}动态规划 这道题目的动态转移方程还是比较好找的。
min_sum(i,j)min(min_sum(i-1,j),min_sum(i-1,j-1))triangle[i][j]
当i0,j0的时候 min_sum(0,0)triangle[0][0]代码实现如下。
public class PascaltriangleTransformV3 {private int[][] triangle new int[][]{new int[]{5},new int[]{7,8},new int[]{2,3,4},new int[]{4,9,6,1},new int[]{2,7,9,4,5}};public int getShortestpathSum(){int m triangle.length;int n triangle[m-1].length;int[][] dp new int[m][n];dp[0][0] triangle[0][0];for(int i1;im;i){for(int j0;ji;j){int val1 (j-1)0?dp[i-1][j-1]:Integer.MAX_VALUE;int val2 (ji-1)?dp[i-1][j]:Integer.MAX_VALUE;dp[i][j] Math.min(val1,val2)triangle[i][j];}}int minPathSum Integer.MAX_VALUE;for(int j0;jn;j){minPathSum Math.min(minPathSum,dp[m-1][j]);}return minPathSum;}}
