Number of ways to build house of cards

impl Solution {
  pub fn house_of_cards(n: i32) -> i32 {
    let n = n as usize;
    // A row with k triangles uses 3k - 1 cards (2k for triangles + k-1 horizontal)
    // Rows must be strictly decreasing in number of triangles from bottom to top
    // DP: dp[cards_remaining] = number of ways
    // We enumerate from bottom up with decreasing k
    
    // dp[remaining] with max_triangles as the upper bound for next row's triangles
    // Recursive: f(remaining, max_k) = sum over k < max_k where 3k-1 <= remaining of f(remaining - (3k-1), k)
    // Base: f(0, _) = 1
    
    let mut dp = vec![vec![-1i32; n + 2]; n + 1];
    
    fn solve(rem: usize, max_k: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
      if rem == 0 {
        return 1;
      }
      if max_k == 0 {
        return 0;
      }
      if dp[rem][max_k] != -1 {
        return dp[rem][max_k];
      }
      let mut res = 0;
      for k in 1..max_k {
        let cost = 3 * k - 1;
        if cost > rem {
          break;
        }
        res += solve(rem - cost, k, dp);
      }
      dp[rem][max_k] = res;
      res
    }
    
    let max_k = (n + 1) / 3 + 1;
    solve(n, max_k, &mut dp)
  }
}