Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...

Design A Leaderboard | biweekly-contest-12 | leetcode | Java solution


Question Source

Java Solution:

class User implements Comparable<User> {
    int id;
    int score;
    
    public User(int id, int score) {
        this.id = id;
        this.score =score;
    }
    
    @Override
    public int compareTo(User u) {
        return u.score - this.score;
    }
    
    @Override
    public String toString(){
        return id +":"+score+" ";
    }
}

class Leaderboard {

    private Set<Integer> ids;
    private List<User> users;
    
    public Leaderboard() {
        this.ids = new HashSet<>();
        this.users = new ArrayList<>();
    }
    
    public void addScore(int playerId, int score) {
        if(!ids.contains(playerId)) {
            ids.add(playerId);
            users.add(new User(playerId, score));
        } else {
            for(User u : users) { 
            
            if(u.id == playerId) {
                u.score+= score;
                break;
            }
        }
        }
    }
    
    public int top(int K) {
        Collections.sort(users);
        System.out.println(K + " " + users);
        
        int sum = 0;
        for(int i = 0; i < K && i < users.size(); i++) {
            sum+= users.get(i).score;
        }
        return sum;
    }
    
    public void reset(int playerId) {
        ids.remove(playerId);
        User del = null;
        for(User u : users) { 
            
            if(u.id == playerId) {
                del = u;
                break;
            }
        }
        
        if(del != null) {
            users.remove(del);
        }
    }
}

Comments

Popular posts from this blog

Array Transformation | biweekly-contest-12 | leetcode | Java Solution

Dynamic Programming: Basics and a Practical Example

leetcode | Longest Substring Without Repeating Characters Solution