动态规划算法

1. 例题讲解

1.1 内容

求arr[1,2,4,1,7,8,3]中选取若干不连续的数字的的最大和。

1.2 解题思路

• [1] 动态规划问题的核心在于重叠子问题.
• [2] 将问题转换为对某一个数字的的选与不选，可以将情况分为2大类：
  
  • 若选取第i个数字，则 A = opt(i-2) + arr[i];
  • 若不选取第个数字，则 B = opt(i-1);
• [3] 取两者的最大值作为最后的选择结果，即为最优解。

1.3 动态规划的出口/初始条件

• opt[0] = arr[0];
• opt[1] = max(arr[0],arr[1]);

1.4 Python3 代码实现

# 动态规划非递归版
import numpy as np
arr = [1,2,4,1,7,8,3]
def dp_opt(arr):
    opt = np.zeros(len(arr))
    opt[0] = arr[0]
    opt[1] = max(arr[0],arr[1])
    for i in range(2,len(arr)):
        opt[i] = max(opt[i-2] + arr[i] ,opt[i-1])
    return opt[len(arr)-1]
print(dp_opt(arr))

2.1 题目内容

从arr[3,34,4,12,5,2]中选取若干数字，判断是否存在一个和为S的序列.

2.2 解题思路

• 同样考虑某个数字选与不选，分为两种情况：
  
  • 若选择第i个数字：A = subset(arr, i-1, S-arr[i]);
  • 若不选择第i个数字：A = subset(arr, i-1, S);
• 取两者的并集(A or B)即可. (只要有一种情况满足即为正确)

2.3 动态规划的出口/初始条件

• if(S==0) retutn True;
• if(i==0) return arr[0] == S;
• if(arr[i] > S) return subset(arr, i-1, S);

2.4 Python3 代码实现

# 动态规划非递归版
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]
dp_subset(arr,9)