LC-楊輝三角-記憶版
上一篇：LC-楊輝三角
上一篇講了楊輝三角的算法，不過之前的算法存在一個問題，比如：文章來源：http://www.zghlxwxcb.cn/news/detail-638950.html
a[5][3] = a[4][2] + a[4][3]
a[5][4] = a[4][3] + a[4][4]
我們可以看到計算a[5][3]和a[5][4]時都需要a[4][3]的值，之前我們是需要每次用到都重新計算，這樣就比較耗時，有沒有辦法記住已經(jīng)算過的值呢，當(dāng)下次用的時候直接獲取就不用重新計算了，以空間來換取時間。
我們可以新增一個二維數(shù)組，把計算的結(jié)果放到數(shù)組中，每次計算前先查看一下數(shù)組中是否存在，如果已存在就獲取值，不存在再計算。
下面是修改后的代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-638950.html
public List<List<Integer>> generate(int numRors){
int[][] catchs = new int[numRors][numRors];
List<List<Integer>> a = new ArrayList<List<Integer>>();
for (int k = 0; k < numRors; k++) {
List temp= new ArrayList();
for (int l = 0; l <= k; l++) {
System.out.print(f(catchs,k, l)+" ");
temp.add(f(catchs,k, l));
}
a.add(temp);
System.out.println();
}
return a;
}
private int f(int[][] catchs,int i, int j) {//0 1
if (j == 0 || i == j) {
return 1;
}
if(catchs[i][j] != 0){
return catchs[i][j];
}
int i1 = f(catchs, i - 1, j - 1) + f(catchs, i - 1, j);
catchs[i][j] = i1;
return i1;
}
到了這里，關(guān)于LC-楊輝三角-記憶版的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[LeetCode] #118 楊輝三角](https://imgs.yssmx.com/Uploads/2024/02/614420-1.gif)
