我们需要在屏幕上写N个相同的字符，每次我们可以插入一个字符，删除最后一个字符，复制并粘贴所有已写字符，即复制操作后，总已写字符数将增加两倍。现在我们有时间插入、删除和复制。我们需要使用这些操作输出在屏幕上写入N个字符的最短时间。
null
例如：
Input : N = 9 insert time = 1 removal time = 2 copy time = 1Output : 5N character can be written on screen in 5 time units as shown below,insert a character characters = 1 total time = 1again insert character characters = 2 total time = 2copy characters characters = 4 total time = 3copy characters characters = 8 total time = 4insert character characters = 9 total time = 5
我们可以用动态规划来解决这个问题。在手工解决一些例子后，我们可以观察到一种模式，对于书写每个字符，我们有两种选择，要么通过插入获取，要么通过复制获取，以花费较少时间的为准。现在写下相应的关系， 让dp[i]成为在屏幕上书写i字符的最佳时间，
If i is even then, dp[i] = min((dp[i-1] + insert_time), (dp[i/2] + copy_time))Else (If i is odd) dp[i] = min(dp[i-1] + insert_time), (dp[(i+1)/2] + copy_time + removal_time)
如果是奇数，则会增加删除时间，因为当复制（i+1）/2个字符时，屏幕上会出现一个需要删除的额外字符。
C++
// C++ program to write characters in // minimum time by inserting, removing // and copying operation #include <bits/stdc++.h> using namespace std; // method returns minimum time to write // 'N' characters int minTimeForWritingChars( int N, int insert, int remove , int copy) { if (N == 0) return 0; if (N == 1) return insert; // declare dp array and initialize with zero int dp[N + 1]; memset (dp, 0, sizeof (dp)); // first char will always take insertion time dp[1] = insert; // loop for 'N' number of times for ( int i = 2; i <= N; i++) { /* if current char count is even then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy */ if (i % 2 == 0) dp[i] = min(dp[i-1] + insert, dp[i/2] + copy); /* if current char count is odd then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy and one extra character deletion*/ else dp[i] = min(dp[i-1] + insert, dp[(i+1)/2] + copy + remove ); } return dp[N]; } // Driver code int main() { int N = 9; int insert = 1, remove = 2, copy = 1; cout << minTimeForWritingChars(N, insert, remove , copy); return 0; } |
JAVA
// Java program to write characters in // minimum time by inserting, removing // and copying operation public class GFG{ // method returns minimum time to write // 'N' characters static int minTimeForWritingChars( int N, int insert, int remove, int copy) { if (N == 0 ) return 0 ; if (N == 1 ) return insert; // declare dp array and initialize with zero int dp[] = new int [N + 1 ]; // first char will always take insertion time dp[ 1 ] = insert; // loop for 'N' number of times for ( int i = 2 ; i <= N; i++) { /* if current char count is even then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy */ if (i % 2 == 0 ) dp[i] = Math.min(dp[i- 1 ] + insert, dp[i/ 2 ] + copy); /* if current char count is odd then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy and one extra character deletion*/ else dp[i] = Math.min(dp[i- 1 ] + insert, dp[(i+ 1 )/ 2 ] + copy + remove); } return dp[N]; } // Driver code to test above methods public static void main(String []args) { int N = 9 ; int insert = 1 , remove = 2 , copy = 1 ; System.out.println(minTimeForWritingChars(N, insert,remove, copy)); } // This code is contributed by Ryuga } |
Python3
# Python3 program to write characters in # minimum time by inserting, removing # and copying operation def minTimeForWritingChars(N, insert, remove, cpy): # method returns minimum time # to write 'N' characters if N = = 0 : return 0 if N = = 1 : return insert # declare dp array and initialize # with zero dp = [ 0 ] * (N + 1 ) # first char will always take insertion time dp[ 1 ] = insert # loop for 'N' number of times for i in range ( 2 , N + 1 ): # if current char count is even then # choose minimum from result for (i-1) # chars and time for insertion and # result for half of chars and time # for copy if i % 2 = = 0 : dp[i] = min (dp[i - 1 ] + insert, dp[i / / 2 ] + cpy) # if current char count is odd then # choose minimum from # result for (i-1) chars and time for # insertion and # result for half of chars and time for # copy and one extra character deletion else : dp[i] = min (dp[i - 1 ] + insert, dp[(i + 1 ) / / 2 ] + cpy + remove) return dp[N] # Driver Code if __name__ = = "__main__" : N = 9 insert = 1 remove = 2 cpy = 1 print (minTimeForWritingChars(N, insert, remove, cpy)) # This code is contributed # by vibhu4agarwal |
C#
// C# program to write characters in // minimum time by inserting, removing // and copying operation using System; class GFG { // method returns minimum time to write // 'N' characters static int minTimeForWritingChars( int N, int insert, int remove, int copy) { if (N == 0) return 0; if (N == 1) return insert; // declare dp array and initialize with zero int [] dp = new int [N + 1]; for ( int i = 0; i < N + 1; i++) dp[i] = 0; // first char will always take insertion time dp[1] = insert; // loop for 'N' number of times for ( int i = 2; i <= N; i++) { /* if current char count is even then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy */ if (i % 2 == 0) dp[i] = Math.Min(dp[i - 1] + insert, dp[i / 2] + copy); /* if current char count is odd then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy and one extra character deletion*/ else dp[i] = Math.Min(dp[i - 1] + insert, dp[(i + 1) / 2] + copy + remove); } return dp[N]; } // Driver code static void Main() { int N = 9; int insert = 1, remove = 2, copy = 1; Console.Write(minTimeForWritingChars(N, insert, remove, copy)); } } //This code is contributed by DrRoot_ |
Javascript
<script> // Javascript program to write characters in // minimum time by inserting, removing // and copying operation // method returns minimum time to write // 'N' characters function minTimeForWritingChars(N, insert, remove, copy) { if (N == 0) return 0; if (N == 1) return insert; // declare dp array and initialize with zero let dp = new Array(N + 1); for (let i = 0; i < N + 1; i++) dp[i] = 0; // first char will always take insertion time dp[1] = insert; // loop for 'N' number of times for (let i = 2; i <= N; i++) { /* if current char count is even then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy */ if (i % 2 == 0) dp[i] = Math.min(dp[i - 1] + insert, dp[parseInt(i / 2, 10)] + copy); /* if current char count is odd then choose minimum from result for (i-1) chars and time for insertion and result for half of chars and time for copy and one extra character deletion*/ else dp[i] = Math.min(dp[i - 1] + insert, dp[parseInt((i + 1) / 2, 10)] + copy + remove); } return dp[N]; } let N = 9; let insert = 1, remove = 2, copy = 1; document.write(minTimeForWritingChars(N, insert, remove, copy)); // This code is contributed by divyeshrabadiya07. </script> |
输出
5
时间复杂性 ：O（N） 辅助空间： O（N）。
本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
