This content originally appeared on DEV Community and was authored by pastaPicaso
The problem statement was pretty simple,
Intially you a letter A written on the Notepad.
you can either of these 2 operations, however many times.
- copy all the contents of the notepad (partial copy is not allowed)
- paste the content from your copy at any location in the text.
I solved this problem using DP.
which looks very similer in implementation to sieve's algorithm to finding the prime.
here's my solution.
class Solution {
public:
int minSteps(int n) {
vector<int> dp(n+3, INT_MAX);
dp[1] = 0;
for (int i = 2; i<= n;i++) {
if (i % 2==0) {
dp[i] = min(dp[i], dp[i/2]+2);
} else {
dp[i] = min(dp[i], i);
for (int j = 2 * i ,times = 2; j <= n; j+=i, times++) {
dp[j] = min(dp[j], dp[i] + times);
}
}
}
return dp[n];
}
};
This content originally appeared on DEV Community and was authored by pastaPicaso
Print
Share
Comment
Cite
Upload
Translate
Updates
There are no updates yet.
Click the Upload button above to add an update.
APA
MLA
pastaPicaso | Sciencx (2024-08-19T16:31:25+00:00) Leetcode daily. Retrieved from https://www.scien.cx/2024/08/19/leetcode-daily/
" » Leetcode daily." pastaPicaso | Sciencx - Monday August 19, 2024, https://www.scien.cx/2024/08/19/leetcode-daily/
HARVARDpastaPicaso | Sciencx Monday August 19, 2024 » Leetcode daily., viewed ,<https://www.scien.cx/2024/08/19/leetcode-daily/>
VANCOUVERpastaPicaso | Sciencx - » Leetcode daily. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/08/19/leetcode-daily/
CHICAGO" » Leetcode daily." pastaPicaso | Sciencx - Accessed . https://www.scien.cx/2024/08/19/leetcode-daily/
IEEE" » Leetcode daily." pastaPicaso | Sciencx [Online]. Available: https://www.scien.cx/2024/08/19/leetcode-daily/. [Accessed: ]
rf:citation » Leetcode daily | pastaPicaso | Sciencx | https://www.scien.cx/2024/08/19/leetcode-daily/ |
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.