1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// @Title: 和为 K 的最少斐波那契数字数目 (Find the Minimum Number of Fibonacci Numbers Whose Sum Is K)
// @Author: 15816537946@163.com
// @Date: 2022-02-03 10:46:18
// @Runtime: 0 ms
// @Memory: 2 MB
impl Solution {
    pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
        let mut f = vec![1, 1];
        let mut ans = 0;

        while f[f.len() - 1] < k {
            f.push(f[f.len() - 1] + f[f.len() - 2]);
        }

        let mut i = f.len() - 1;
        while k > 0 {
            if k >= f[i] {
                k -= f[i];
                ans += 1;
            }

            i -= 1;
        }
        ans
    }
}