Python-再帰とダイナミックプランニング

タイトル1:
与えられた配列arrは、arr内のすべての値が正数であり、重複しない.各値は1種の額面の貨幣を代表して、各額面の貨幣は任意の枚を使うことができて、更に1つの整数aimが探している金額を代表して、aimを構成する最低の貨幣数を求めます.
例arr=[5,2,10,1],aim=5
考え方:
1、len(arr)行aim+1列行列を定義し、デフォルト値は最大値である.
2、初期化、第1列は0で、第1行は以下の各代表で、aim=0、1、2、3、4、5まで、1枚5元しかかかりません.
0  max max max max 1
0
0
0
3、dp[i][j] = min{dp[i-1][j], dp[i][j-arr[i]+1]} 
dp[i-1][j]は、ローの値を使用しないで直接使用することを表し、dp[i][j-arr[i]+1はローの使用を表す

def findmoney(arr,aim):
    max=float('inf')
    l = [[max for i in range(aim+1)] for i in range(len(arr))]
    for i in range(len(arr)):
        l[i][0]=0
    for i in range(1,aim//arr[0]+1):
        l[0][i*arr[0]]=i
    for i in range(1,len(arr)):
        for j in range(1,aim+1):
            left=max
            if j-arr[i]>=0:
                left=l[i][j-arr[i]]+1
            l[i][j]=min(l[i-1][j],left)
    print(l)
findmoney([5,2,10,1],20)

問題1補足:
与えられた配列arrは、arr内のすべての値が正数であり、重複しない.各値は1枚のお金の額面を表し、各額面の通貨は1枚使用することができ、整数aimを与えて探しているお金の数を表し、aimを構成する最小の通貨数を求める.
1、前の問題の第一歩と同じです.
2、最初の列は前の問題と同じで、最初の行はarr[0]の位置だけを1にします.
3、dp[i][j]=min(dp[i-1][j],dp[i-1][j-arr[i]])
dp[i-1][j]は、ロー通貨を使用しないことを意味する
dp[i-1][j-arr[i]]は、ロー通貨の使用を表します.

def findmoney(arr,aim):
    max=float('inf')
    l = [[max for i in range(aim+1)] for i in range(len(arr))]
    for i in range(len(arr)):
        l[i][0]=0
    l[0][arr[0]]=1
    for i in range(1,len(arr)):
        for j in range(1,aim+1):
            left=max
            if j-arr[i]>=0:
                left=l[i-1][j-arr[i]]+1
            l[i][j]=min(l[i-1][j],left)
    print(l)
    print(l[i][j])
findmoney([5,2,10,1],15)

タイトル2:
与えられた配列arrは、arr内のすべての値が正数であり、重複しない.各値は1種の額面の貨幣を代表して、各額面の貨幣は任意の枚を使うことができて、更に1つの整数aimが探している金額を代表して、両替を求めるのはどれだけの方法がありますか.
例arr=[5,2,10,1],aim=5
考え方:
1、len(arr)行aim+1列マトリクスを定義し、デフォルト値は0です.
2、初期化、第1列は1で、各面の値を表すのはすべて使わないで、1つの方案があって、第1行は以下の各代表で、aim=0、1、2、3、4、5、5まで、1枚5元しか必要ありません.
1  0 0 0 0 1
1  0 1 0 1 0
1
1
3、num=dp[i-1][j-arr[i]*k] for k in range(aim+1); dp[i][j] = num
dp[i-1][j]は、ローの値を使用しないで直接使用することを表し、dp[i][j-arr[i]+1はローの使用を表す

def findmoney(arr,aim):
    # max=float('inf')
    # max=float('inf')
    # num=0
    l = [[0 for i in range(aim+1)] for i in range(len(arr))]
    for i in range(len(arr)):
        l[i][0]=1
    for i in range(1,aim//arr[0]+1):
        l[0][i*arr[0]]=1
    for i in range(1,len(arr)):
        for j in range(1,aim+1):
            num=0
            for k in range(aim+1):
                if j-arr[i]*k>=0:
                    num+=l[i-1][j-k*arr[i]]
            l[i][j]=num
    print(l)
    print(l[i][j])
findmoney([5,2,10,1],10)

最適化手順3:
dp[i][j] = dp[i-1][j]+dp[i][j-arr[i]]

def findmoney(arr,aim):
    # max=float('inf')
    # max=float('inf')
    # num=0
    l = [[0 for i in range(aim+1)] for i in range(len(arr))]
    for i in range(len(arr)):
        l[i][0]=1
    for i in range(1,aim//arr[0]+1):
        l[0][i*arr[0]]=1
    for i in range(1,len(arr)):
        for j in range(1,aim+1):
            l[i][j]=l[i-1][j]
            if j-arr[i]>=0:
                    l[i][j]+=l[i][j-arr[i]]
    print(l)
    print(l[i][j])
findmoney([5,2,10,1],10)

タイトル3:
k個の整数+のシーケンス{N 1,N 2,...,Nk}が与えられ、その任意の連続サブシーケンスは{Ni,Ni+1,...,Nj}として表すことができ、そのうち1<=i<=j<=kである.最大連続サブシーケンスは、すべての連続サブシーケンスの要素と最大の1つであり、例えば、所与のシーケンス{−2,11,−4,13,−5,−2}であり、その最大連続サブシーケンスは{11,−4,13}、最大連続サブシーケンスおよびすなわち20である.

def findmax(arr):
    n=len(arr)
    l=[0 for i in range(n)]
    l[0]=arr[0]
    for i in range(1,n):
        l[i]=max(arr[i]+l[i-1],arr[i])
    print(max(l))
findmax([-2,11,-4,13,-5,-2,14])

問題3拡張:
積の最大シーケンスを出力します.

def find(arr):
    n=len(arr)
    l=[0 for i in range(n)]
    g=[0 for i in range(n)]
    l[0]=arr[0]
    g[0]=arr[0]
    for i in range(1,n):
        l[i]=max(l[i-1]*arr[i],arr[i],g[i-1]*arr[i])
        g[i]=min(l[i-1]*arr[i],arr[i],g[i-1]*arr[i])
    print(l[-1])
find([-2, 11, -4, 13, -5, -2])

タイトル4:
アレックスと李はいくつかの石でゲームをしています.偶数の石が1列に並んでいて、各山には正の整数の石piles[i]があります.
ゲームは誰の手の中の石が一番多いかで勝負を決める.石の総数は奇数なので引き分けはありません.
アレックスと李は交代で行い、アレックスは先に始めた.ラウンドごとに、プレイヤーは行の開始または終了から石の山全体を取り出します.このような状況は、より多くの石の山がないまで続き、この時、手にした石が最も多いプレイヤーが勝った.
アレックスと李が最高のレベルを発揮したと仮定すると、アレックスが試合に勝ったときはtrue、李が試合に勝ったときはfalseに戻る.
例:

  ：[5,3,4,5]
  ：true
  ：
       ，     5     5     。
       5  ，        [3,4,5] 。
       3  ，       [4,5]，        5     10  。
       5  ，       [3,4]，        4     9  。
   ，   5                   ，       true 。

def stoneGame(piles):
    n = len(piles)
    dp = piles[:]

    for d in range(1, n):
        for i in range(n - d):
            dp[i] = max(piles[i] - dp[i + 1], piles[i + d] - dp[i])
    # print(dp)
    print(dp[0])
stoneGame([5,3,4,5])