Блог

Я пытаюсь решить проблему с минимальными затратами на подъем по лестнице.

Вот ссылка: https://leetcode.com/problems/min-cost-climbing-stairs/

Я написал рекурсивную версию решения, и она работала для примеров тестовых случаев, и, очевидно, она показала TLE для остальных случаев. Вот рекурсивная версия:

 int solve(int[] arr, int idx, int cost) {
        if(idx >= arr.length) return cost;
         
        return Math.min(solve(arr, idx   1, cost   arr[idx]), 
                       solve(arr, idx   2, cost   arr[idx]));
}
 

Теперь проблема в том, что, когда я пытаюсь запомнить это с помощью 1-d массива, я также не получаю правильных ответов для примеров.

Вот мемуарная версия:

 int[] t;
    Solution() {
        this.t = new int[1001];
    }
    
    public int minCostClimbingStairs(int[] arr) {
        int n = arr.length;
        Arrays.fill(t, -1);
        
        return Math.min(solve(arr, 0, 0), solve(arr, 1, 0));
    }
    
    int solve(int[] arr, int idx, int cost) {
        if(idx >= arr.length) return cost;
        
        if(t[idx] != -1) return t[idx];
        
        return t[idx] = Math.min(solve(arr, idx   1, cost   arr[idx]), 
                       solve(arr, idx   2, cost   arr[idx]));
    }
 

Чего мне не хватает?
Заранее спасибо.

От Нуба в DP.