Algorithm: Leetcode Contest 401

3179. Find the N-th Value After K Seconds

Solution

class Solution {
    public int valueAfterKSeconds(int n, int k) {
        int[] a = new int[n];
        Arrays.fill(a, 1);
        
        while(k != 0) {
            for(int i = 1; i < a.length; i++) {
                a[i] = (a[i] + a[i - 1]) % (int)(Math.pow(10, 9) + 7);
            }
            
            k--;
        }
        
        return a[n - 1];
    }
}

Retro

I didn’t perform modulo operation in each iteration, instead I only perform modulo at the end, then it cannot get the correct answer, no matter I use long type or double type.

so in the future, if there is any modulo are required, perform it as frequent as possible, to ensure any intermediate value is incorrect

3180. Maximum Total Reward Using Operations I

Solution

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        Map<String, Integer> cache = new HashMap<>();
        return dfs(0, 0, rewardValues, cache);
    }
    
    // start from index, biggest value can be derived from following 
    private int dfs(int curIndex, int curSum, int[] rewardValues, Map<String, Integer> cache) {
        if (curIndex == rewardValues.length) {
            return curSum;
        }
        String key = curIndex + "_" + curSum;
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        
        int withoutCur = dfs(curIndex + 1, curSum, rewardValues, cache);
        int withCur = 0;
        if (rewardValues[curIndex] > curSum) {
            withCur = dfs(curIndex + 1, curSum + rewardValues[curIndex], rewardValues, cache);
        }
        
        cache.put(key, Math.max(withoutCur, withCur));
        return cache.get(key);
    }
}

use map as cache.