650. 2 Keys Keyboard

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #matrix #medium #sliding-window

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. given số nguyên n, return минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Ví dụ:

Input: n = 3

Output: 3

C# lời giải

đã khớp/gốc

public class Solution {
    public int MinSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.Min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSteps(int n) {
        if (n == 1) return 0;
        vector<int>& dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

Java lời giải

đã khớp/gốc

public class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

JavaScript lời giải

đã khớp/gốc

var minSteps = function(n) {
    if (n === 1) return 0;
    const dp = new Array(n + 1).fill(0);
    for (let i = 2; i <= n; i++) {
        dp[i] = i;
        for (let j = 1; j <= i / 2; j++) {
            if (i % j === 0) {
                dp[i] = Math.min(dp[i], dp[j] + i / j);
            }
        }
    }
    return dp[n];
};

Python lời giải

đã khớp/gốc

def minSteps(n):
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = i
        for j in range(1, i // 2 + 1):
            if i % j == 0:
                dp[i] = min(dp[i], dp[j] + i // j)
    return dp[n]

Go lời giải

đã khớp/gốc

package main

import (
    "fmt"
    "math"
)

func minSteps(n int) int {
    if n == 1 {
        return 0
    }
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        dp[i] = i
        for j := 1; j <= i/2; j++ {
            if i%j == 0 {
                dp[i] = int(math.Min(float64(dp[i]), float64(dp[j]+i/j)))
            }
        }
    }
    return dp[n]
}

Algorithm

Используйте dynamic programming для отслеживания минимального количества операций, необходимых для достижения определенного количества 'A' на экране.

Итерируйтесь от 1 до n, проверяя все возможные делители текущего числа и обновляя минимальное количество операций для каждого числа.

Возвращайте значение из таблицы динамического программирования для n.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.