我們現在對楊輝三角進行一些改造。每個位置的數字可以隨意填寫，經過某個數字只能到達下面一層相鄰的兩個數字。

假設你站在第一層，往下移動，我們把移動到最底層所經過的所有數字之和，定義為路徑的長度。請你編程求出從最高層移動到最底層的最短路徑長度。

分析

題目的目標是：到 最底層的最短路徑長度 。
目標狀態是：到達最底層。
分階段：按照到達第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 j=0;j<n;j++){minPathSum = Math.min(minPathSum,f(m-1,j));}return minPathSum;}/*** 到達第i層,第j列的最短路徑和* @param i*/private int f(int i, int j) {if(j<0) return Integer.MAX_VALUE;//此路不同if(j>=triangle[i].length) return Integer.MAX_VALUE;//此路不同if(i==0){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 j=0;j<n;j++){minPathSum = Math.min(minPathSum,f(m-1,j,memo));}return minPathSum;}private int f(int i, int j,int[][] memo) {if(j<0) return Integer.MAX_VALUE;//此路不同if(j>=triangle[i].length) return Integer.MAX_VALUE;//此路不同if(i==0){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] 當i=0,j=0的時候 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 i=1;i<m;i++){for(int j=0;j<=i;j++){int val1 = (j-1)>=0?dp[i-1][j-1]:Integer.MAX_VALUE;int val2 = (j<=i-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 j=0;j<n;j++){minPathSum = Math.min(minPathSum,dp[m-1][j]);}return minPathSum;}}

總結

以上是生活随笔為你收集整理的动态规划——变形的杨辉三角形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。