[珂太]ダイナミックプログラミング-1699,平方和

6126 ワード
テキストリンク
1699平方和
📒 アルゴリズムタイプ
  • 動的プログラミング
    • 📁 問題のソース
    https://www.acmicpc.net/problem/1699
    💡 アイデア
  • 平方の最大数から開始し、-->整数nを加算して
    • を作成します.
  • 最大数から増加すると、n=32(25+4+1)5:x/n=32(16+16)2:o
    • などの異常が発生する可能性があります.
    📌 マイコード
    -間違った答え:
    n=int(input())
k=0
num=[]
while(True):
  if(k*k>n):break
  num.append(k*k)
  k+=1
def max_maker(n,num):
  for number in num:
    if(number>n):
      break
    max=number
  return max

p=n
result=0
while True:
  
  p=p-max_maker(p,num)
  result+=1 
  if p==0:
    break
print(result)
    -パス:
    n = int(input())
 
dp = [i for i in range (n+1)]
 
for i in range(1, n+1):
    for j in range(1, i):
        if (j * j) > i:
            break
        if dp[i] > dp[i - j * j] + 1:
            dp[i] = dp[i - j * j] + 1
 
print(dp[n])
  • dpアルゴリズムを用いて問題を解決する
    • 考察する
  • dpアルゴリズムの問題に初めて接触した.
  • 複数種類のDPアルゴリズム
    • を解いて適用する
    📌 リファレンスコード
    CSSフロート付きルックブック
    Androidはパッケージ名でアプリケーションを起動します