動态規劃python

1.定義

動态規劃（英語：Dynamic planning，簡稱 DP），是一種在數學、管理科學、計算機科學、經濟學和生物資訊學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動态規劃常常适用于有重疊子問題和最優子結構性質的問題。

2.核心思想

把一個複雜問題不斷拆分為子問題，逐個來解決。

萬能公式：

1. dp[i]，dp[i][j]表示的含義；
2. dp轉換狀态：dp[i] = f(dp[j])
3. base case,即出口

3.例子

對于數列arr = [1，2，4，1，7，8，3]，如何選擇才能使得到的值最大，限制：相鄰元素不可取。

import numpy as np
arr = [1,2,4,1,7,8,3]
def dp_opt(arr):
  opt = np.zeros(len(arr)) #用0占位
  opt[0] = arr[0]          #出口
  opt[1] =max(arr[0],arr[1])    #出口
  for i in range(2,len(arr)):   
     A = opt[i-2] + arr[i]     #遞歸式子
     B = opt[i-1]
     opt[i] = max(A,B)
  return opt[len(arr)-1]
print(dp_opt(arr))
           

對于數列arr = [3,34,4,12,5,2]，取出幾個數字，使得相加為9。

arr = [3,34,4,12,5,2]
def rec_subset(arr,i,s):
    if s == 0:
        return True
    elif i == 0:
        return arr[0] == s
    elif arr[i] > s:
        return rec_subset(arr,i-1,s)
    else:
        A = rec_subset(arr,i-1,s-arr[i])
        B = rec_subset(arr,i-1,s)
        return A or B
print(rec_subset(arr,len(arr)-1,9))
           

import numpy as np
arr = [3,34,4,12,5,2]
def dp_subset(arr,S):
    subset = np.zeros((len(arr),S+1),dtype=bool)
    subset[:,0] = True
    subset[0,:] = False
    subset[0,arr[0]] = True
    for i in range(1,len(arr)):
        for s in range(1,S+1):
            if arr[i] > s:
                subset[i,s] = subset[i-1,s]
            else:
                A = subset[i-1, s-arr[i]]
                B = subset[i-1,s]
                subset[i,s] = A or B
    r,c = subset.shape
    return subset[r-1,c-1]
print(dp_subset(arr,9))