DynamicProgramming动态规划
2018-04-22 本文已影响21人
LittleSasuke
Welcome To My Blog
刚接触动态规划,突然发现这是个很大的领域,所以就先通过别人的分享以及做题逐步总结了.
DynamicProgramming
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions
维基百科说动态规划是解决复杂问题的方法,通过三点实现:
- 将原问题分解为简单的子问题(subproblem)
- 每个子问题只解决一次
- 存储每个子问题的解
解题思路
- 将原问题分解为子问题
- 确定状态
状态就是每个子问题所能取到的值,所有状态构成了状态空间 - 确定边界值(初始状态)
- 确定递推方程(状态转移方程)
经验
解题过程中的体会
- 对于当前下标对应的元素,选还是不选
-
从后向前分析,从边界(从前)开始向后实现
- 实现时,使用递归时先写边界条件;使用数组时先写边界条件(或者说从边界开始推)
- 使用时,输入最后一个索引
- 递归版本:各种情况下要return;循环版本:更新某个值而不是return了!
例题
1
给定一串数字1,2,4,1,7,8,3,现从中取出某几个数字,使这些数字的和最大(不能取相邻的数字)
1.png
python
#递归版,包含大量重叠子问题,换成循环版
def rec_opt(arr,i):
if i == 0: return arr[0]
elif i == 1:return max(arr[0],arr[1])
else:
A = rec_opt(arr,i-2)+arr[i]
B = rec_opt(arr,i-1)
return max(A,B)
arr = [1,2,4,1,7,8,3]
print(rec_opt(arr,len(arr)-1))
#循环版
import numpy as np
opt = np.zeros(len(arr))
opt[0] = arr[0]
opt[1] = max(opt[0],opt[1])
for i in range(2,len(arr)):
A = opt[i-2] + arr[i]
B = opt[i-1]
opt[i] = max(A,B)
print(opt[len(arr)-1])
java
正好学习java中,附带java版本
//递归版
class Solution {
public static int rec_opt(int[] arr,int index) {
if(index==0) return arr[0];
else if(index==1) return Math.max(arr[0],arr[1]);
else {
int A = rec_opt(arr,index-2)+arr[index];
int B = rec_opt(arr,index-1);
return Math.max(A,B);
}
}
public static void main (String[] args){
int[] arr = {1,2,4,1,7,8,3};
int res = rec_opt(arr,arr.length-1);
System.out.print(res);
}
}
//循环版
class Solution {
public static void main (String[] args){
int[] arr = {1,2,4,1,7,8,3};
int[] opt = new int[arr.length];
//从边界开始向后实现
opt[0] = arr[0];
opt[1] = Math.max(arr[0],arr[1]);
for (int i = 2; i<arr.length;i++){
int A = opt[i-2] + arr[i];
int B = opt[i-1];
opt[i] = Math.max(A,B);
}
System.out.print(opt[arr.length-1]);
}
}
2
给定一串数字3,34,4,12,5,2,现从中取出某几个数字,使这些数字的和为S(S为某个整数,选出的数字不能是相邻的)
2.png
python
#递归版
def rec_okay(arr,i,S):
if i==0:return arr[0]==S
elif i==1:
A = arr[1] == S
B = arr[0] == S
return A or B
elif S==0: return True
elif arr[i]>S: return rec_okay(arr,i-1,S)
else:
A = rec_okay(arr,i-2,S-arr[i])
B = rec_okay(arr,i-1,S)
return A or B
arr = [3,34,4,12,5,2]
print(rec_okay(arr,len(arr)-1,9))
print(rec_okay(arr,len(arr)-1,10))
#循环版
#i是索引,j是当前结果s
import numpy as np
def okay(arr,S):
okay = np.zeros((len(arr),S+1),dtype=bool)
#从边界向后推,所以先给出边界情况
okay[0,:] = False
okay[0,arr[0]] = True
okay[:,0] = True
for i in range(2,len(arr)):
for j in range(1,S+1):
if i == 1:
okay[1,j] = (arr[1] == j) or (arr[0] == j)
elif arr[i]>j:
okay[i,j] = okay[i-1,j]
else:
A = okay[i-2,j-arr[i]]
B = okay[i-1,j]
okay[i,j] = A or B
#从边界向后推,直至推导要求的位置
return okay[len(arr)-1,S]
arr = [3,34,4,12,5,2]
print(okay(arr,9))
print(okay(arr,10))
java
//递归版
class Solution {
public static boolean rec_okay(int[] arr, int index, int sum) {
if (index == 0) return arr[0] == sum;
else if (index == 1) return (arr[1] == sum) || (arr[0] == sum);
else if (sum == 0) return true;
else if (arr[index] > sum) return rec_okay(arr, index - 1, sum);
else {
boolean A = rec_okay(arr, index - 2, sum - arr[index]);
boolean B = rec_okay(arr, index - 1, sum);
return A || B;
}
}
public static void main(String[] args) {
int[] arr = {3, 34, 4, 12, 5, 2};
boolean res = rec_okay(arr, arr.length - 1, 9);
System.out.println(res);
boolean res2 = rec_okay(arr, arr.length - 1, 10);
System.out.println(res2);
}
}
//循环版
class Solution {
public static boolean okay(int[] arr,int sum) {
boolean[][] okay = new boolean[arr.length][sum+1];
for(int j = 0;j <= sum;j++) okay[0][j] = j == arr[0];
for(int j = 0;j <= sum;j++) okay[1][j] = (arr[1] == j)|| (arr[0] == j);
for(int i = 0; i < arr.length; i++) okay[i][0] = true;
for(int i = 1; i<arr.length; i++){
for(int j = 1; j<=sum; j++){
//如果当前的数字大于当前的结果,则只有一个选项:不能选当前数字
if(arr[i]>j) okay[i][j] = okay[i-1][j];
else okay[i][j] = okay[i-2][j-arr[i]] || okay[i-1][j];
}
}
return okay[arr.length-1][sum];
}
public static void main(String[] args) {
int[] arr = {3, 34, 4, 12, 5, 2};
boolean res = okay(arr, 9);
System.out.println(res);
boolean res2 = okay(arr,10);
System.out.println(res2);
}
}
3
3.png
在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。
4.png
python
#递归版
import numpy as np
def rec_opt(arr,i,j):
if i==0:return arr[0,j]
else: return max(rec_opt(arr,i-1,j),rec_opt(arr,i-1,j+1))+arr[i,j]
arr = np.array([[4,5,2,6,5],[2,7,4,4,0],[8,1,0,0,0],[3,8,0,0,0],[7,0,0,0,0]])
print(rec_opt(arr,4,0))
#循环版
import numpy as np
arr = np.array([[4,5,2,6,5],[2,7,4,4,0],[8,1,0,0,0],[3,8,0,0,0],[7,0,0,0,0]])
#第0行的值不变,从第一行开始调整
for i in range(1,5):
for j in range(0,5-i):
arr[i,j] = max(arr[i-1,j],arr[i-1,j+1]) + arr[i,j]
print (arr[4,0])
java
//递归版
class Solution {
public static int rec_opt(int[][] arr,int i, int j) {
if (i == 0) return arr[0][j];
else return Math.max(rec_opt(arr,i-1,j),rec_opt(arr,i-1,j+1)) + arr[i][j];
}
public static void main(String[] args) {
int[][] arr = {{4,5,2,6,5},{2,7,4,4,0},{8,1,0,0,0},{3,8,0,0,0},{7,0,0,0,0}};
int res = rec_opt(arr,4,0);
System.out.println(res);
}
}
//循环版
class Solution {
public static void main(String[] args) {
int[][] arr = {{4,5,2,6,5},{2,7,4,4,0},{8,1,0,0,0},{3,8,0,0,0},{7,0,0,0,0}};
//第0行不变,从第1行开始调整
for(int i = 1; i < 5; i++)
for(int j = 0; j < 5 - i; j++){
arr[i][j] = Math.max(arr[i-1][j],arr[i-1][j+1]) + arr[i][j];
}
System.out.println(arr[4][0]);
}
}
参考:
正月点灯笼
教你彻底学会动态规划——入门篇
