阅读量:2
// 动态规划 pub fn generate(num_rows: i32) -> Vec<Vec<i32>> { let mut triangle: Vec<Vec<i32>> = vec![]; for i in 0..num_rows { let mut row = vec![1; (i + 1) as usize]; for j in 1..i as usize { row[j] = triangle[(i - 1) as usize][(j - 1)] + triangle[(i - 1) as usize][j]; } triangle.push(row); } triangle } use std::collections::HashMap; // 递归（带缓存） struct Solution; impl Solution { pub fn generate(num_rows: i32) -> Vec<Vec<i32>> { let mut cache = HashMap::new(); let mut triangle = vec![]; for i in 0..num_rows { let mut row = vec![]; for j in 0..=i { row.push(Self::get_value(i, j, &mut cache)); } triangle.push(row); } triangle } fn get_value(i: i32, j: i32, cache: &mut HashMap<(i32, i32), i32>) -> i32 { if j == 0 || j == i { return 1; } if let Some(&val) = cache.get(&(i, j)) { return val; } let val = Self::get_value(i - 1, j - 1, cache) + Self::get_value(i - 1, j, cache); cache.insert((i, j), val); val } } // 迭代 pub fn generate2(num_rows: i32) -> Vec<Vec<i32>> { let mut triangle: Vec<Vec<i32>> = Vec::with_capacity(num_rows as usize); for i in 0..num_rows as usize { let mut row = vec![1; i + 1]; for j in 1..i { row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]; } triangle.push(row); } triangle } fn main() {} 