如何使用給定的四個鍵打印A的最大數量


難度級別
經常問 亞馬遜 Facebook 谷歌 貝寶 Paytm
動態編程

問題陳述

如何使用給定的四個鍵打印A的最大數量,此問題表明您可以選擇要按下的鍵。 這些鍵執行以下任務:

  1. Key1 –在屏幕上打印“ A”
  2. Key2 –選擇整個屏幕。
  3. Key3 –複製所選內容。
  4. Key4 –打印複製的內容。

您只能按N次鍵,找出可以打印的最大A數。 通過使用您可以進行的任何組合,找到可以打印的最大A數。

Number of keys that can be pressed = 2
Number of A's that can be printed = 2

說明:由於任何其他組合都無法找到更好的結果。 使用任何其他組合的按鍵,將無法打印更多數量的A。 我們可以嘗試任何其他組合。 假設我們只打印一個A。因為如果不打印'A',就無法選擇'A',然後再打印它。 因此,最好打印單個“ A”。 之後,我們可以執行選擇,打印和復印這三種組合中的任何一種。 但是,這些組合中的任何一種都無法提供更好的結果。

如何使用給定的四個鍵打印A的最大數量

Number of keys that can be pressed = 6
Number of A's that can be printed = 6

說明:我們將使用以下6個按鍵:Key1(打印'A'),Key1,Key1,Key2(選擇整個屏幕內容),Key3(複製所選內容),Key4(打印複製的內容)。 可能還有其他按鍵可以打印相同數量的A。

途徑

如果我們從按鍵數= N-3到1並嘗試找出A的最大數量,就可以找到使用給定的四個鍵來打印A的最大數量的方法。
我們將認為第ith個位置是我們按Key2,Key3,然後按Key4序列的起點。 現在,如果我們從N-3循環到1。可能會有很多這樣的點。

與往常一樣,我們需要一個基本案例,因為問題在於 動態編程。 在這種情況下,如果n <= 6,我們僅打印數字。 為什麼我們這樣稱呼 動態編程 即使在代碼中我們不使用任何DP陣列? 因為該問題滿足兩個條件:子問題重疊和最優子結構。 每個問題都可以進一步細分,然後再進一步細分。

推薦碼

C ++代碼查找可以打印的最大As數

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

int maximumNumberOfAsPrinted(int numberOfKeyPresses)
{
  if(numberOfKeyPresses <= 6)
    return numberOfKeyPresses;

  int maxNumberOfAs = 0;
  for(int i = numberOfKeyPresses-3; i>=1;i--) {
    // here we consider that after ith keystroke we are performing only selection, copy once and then paste
    // thus starting from numberOfKeyPresses-3
    int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    if (numberOfAs > maxNumberOfAs)
      maxNumberOfAs = numberOfAs;
  }
  return maxNumberOfAs;
}

int main()
{
  int numberOfKeyPresses;cin>>numberOfKeyPresses;
  int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
  cout<<numberOfAsPrinted;
}
18
192

Java代碼查找可以打印的最大As數

import java.util.*;

class Main{
    static int maximumNumberOfAsPrinted(int numberOfKeyPresses)
    {
    	if(numberOfKeyPresses <= 6)
    		return numberOfKeyPresses;
    
    	int maxNumberOfAs = 0;
    	for(int i = numberOfKeyPresses-3; i>=1;i--) {
    		// here we consider that after ith keystroke we are performing only selection, copy once and then paste
    		// thus starting from numberOfKeyPresses-3
    		int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    		if (numberOfAs > maxNumberOfAs)
    			maxNumberOfAs = numberOfAs;
    	}
    	return maxNumberOfAs;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int numberOfKeyPresses = sc.nextInt();
    	int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
    	System.out.println(numberOfAsPrinted);
    }
}
18
192

複雜度分析

時間複雜度: 上)

由於我們只是在許多按鍵上運行了一個循環。 該算法的線性時間複雜度為O(N)。

空間複雜度:O(1)

由於我們僅存儲一些特定的整數和元素。 我們有恆定的空間複雜性。