动态规划和递归一样
还是要找一个出口
主要区别是要找一个列表将之间的子问题的答案储存起来

一.寻找最大值

在这个数组中，不能选相邻的
找出选出数字之和最大的数字

解：

出口：

①递归：

arr = [1, 2, 4, 1, 7, 8, 3]


def rec_opt(arr, i):     # 选择第i个
    if i == 0:			# 只有第0个的话，就是他自己
        return arr[0]    
    elif i == 1:		# 第1个的话，找前两个最大的
        return max(arr[0], arr[1])
    else:				# 其他情况分为选或者不选
        A = rec_opt(arr, i - 2) + arr[i]	# 选第i的话，是他自己的权重 + 与他不相邻且之前的权重最大值
        B = rec_opt(arr, i - 1)				# 不选的话，就是前一个
        return max(A, B)					# 在选与不选之间挑一个最大的
        
rec_opt(arr, 6)

② 动态规划

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)):
        A = opt[i-2] + arr[i]
        B = opt[i-1]
        opt[i] = max(A, B)
        
    return opt[len(arr) - 1]

dp_opt(arr)

二.寻找和式

在一个数组中，我们给定一个数
看能否在这个数组中找到一组式子之和等于给定的这个数字

①递归

arr = [3, 34, 4, 12, 5, 2]

def rec_subset(arr, i , s):   # 第i个，给定数字是s
    if s == 0:                # s是0，肯定能找出一个和式
        return True
    elif i == 0:              # 第0个的话,看arr[0]是否等于s，相等的话就能找出
        return arr[0] == s
    elif arr[i] > s:          # 如果arr[i] > s,继续向后找，即不选这个数
        return rec_subset(arr, i-1, s)
    else:
        A = rec_subset(arr, i-1, s-arr[i])    # 选择这个数，s把选择的数减去
        B = rec_subset(arr, i-1, s)           # 不选择这个数，s保留
        return A or B                        # 找一个能找出和式的
    
rec_subset(arr, len(arr)-1, 9)

② 动态规划
在这里我们要定一个二维数组来储存子问题的答案

左边的表示数组中的元素
上边的表示s，因为每次会减，所以s的可能值就是 0~9
如果左边的能组成上边的，就是True

import numpy as np

arr = [3, 34, 4, 12, 5, 2]

def dp_subset(arr, S):   # s是给定的数字
    subset = np.zeros((len(arr), S + 1), dtype = bool)
    subset[:, 0] = True              # 0列所有行都是True(都能组成0)
    subset[0, :] = False             # 0行所有列都是False
    subset[0, arr[0]] = True         # 但是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)

注：这里的能否找到，看0~i下标的元素能否组成给定数
比如 4 虽然比 3 大，但是从 3 到 4(下标从0到2)的元素中，arr[0]是可以组成3
的，也就是说，我们找的是从arr[0]~arr[i]的元素中能否找到数字组成给定S。
所以我们找最右下角的意思，就是从arr[0]~arr[5]中能否找到组成9的

二.求最长子序列长度

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#define NUM 100
using namespace std;

int son_ans[NUM][NUM];

void LCSLnegth(int x_len, int y_len, const char x[], char y[])
{
	int i,j;
	// 0行和0列都是0，因为只有一个元素的集合没有真子集 
	for(i = 1;i <= x_len;i++)  son_ans[i][0] = 0;
	for(j = 1;j <= y_len;j++)  son_ans[0][i] = 0;
	
	// 构造数组son_ans，最后输出右下角的答案 
	// son_ans[i][j] 表示Xi和Yi的最长公共子序列的长度 
	for(i = 1;i <= x_len;i++){
		for(j = 1;j <= y_len;j++){
			if(x[i] == y[j])
				son_ans[i][j] = son_ans[i-1][j-1] + 1; // 之前的加上这次的
			else if (son_ans[i-1][j] >= son_ans[i][j-1])
				son_ans[i][j] = son_ans[i-1][j];
			else 
				son_ans[i][j] = son_ans[i][j-1] ;
		}
	}
 } 

int main() 
{
	int x_len = 7;
	int y_len = 6;
	char X[x_len] = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
	char Y[y_len] = {'B', 'D', 'C', 'A', 'B', 'A'};
	
	LCSLnegth(x_len, y_len, X, Y);
	cout << son_ans[x_len][y_len];
}           

相关概念：
状态：子问题相关的各个变量的一组取值。
无后效性：子问题的解取值与解题路径无关。

动态规划：

解题步骤：
1.将原问题分解为子问题。
2.确定状态。
3.确定边界状态。
4.确定状态转移方程。
特点：
1.问题具有最优子结构
2.无后效性。

求最长子序列的算法问题描述：

解题思路：
1.将原问题分解为子问题，并且子问题满足无后效性。
以 a[i]为终点 对应的最长序列为子问题。
2.确定状态。
maxLen（a【i】）=maxLen（a【k】）+1，其中a【k】为小于a【i】的数.
3.确定边界状态。
当a【i】为第一个数时，对应的maxLen=1.
4.方程确定。
maxLen（a【i】）=maxLen（a【k】）+1 （ i！=0）
maxLen=1. （i>0）

java代码：

	/**
	 * 
	 * @param k   要求的以此数字为终点的子序列对应数组下标
	 * @param arr 传入的数组
	 * @return 最长原序列子序列长度
	 */
	static public int maxLen(int k, int[] arr) {
		int j = 0; // 比arr[k]小的，且距离最近
		int tempLen=0;
		String temp="";
		if (k == 1) {
			return 1;
		} else {              
			for (int i = k - 1; i >= 0; i--) {
				if (arr[i] < arr[k]) {
					j+=1;
					
					temp=temp+","+Integer.toString(i);    //会多出一个逗号，如",1,2,3,4"
					
				}
			}
			if (j != 0) {
				temp=temp.substring(1,temp.length());//去掉第一个“,”
				String [] e=temp.split(",");  //去掉逗号存放在字符串数组
				
				for(String b:e) {
					j=Integer.parseInt(b);
					if(tempLen<maxLen(j, arr))
					tempLen=maxLen(j, arr);
				}
				return  tempLen+ 1;
			} else {
				return 1;
			}
		}

	

最长公共子序列：

链接：https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172
题目：
我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

题解：给定我们两个字符串求解最长的公共子序列，并且公共串是可以不连续，也就是说只要要找两个字符串公共子串的最长长度；

如果采取暴力方法，我们可以分别求出字符串m的所有子串存于set容器中，在求出字符串n的所有子串，进行查询，找出最长的公共子串，但是这种方法的效率极低。

所以我们将回到本篇的标题：动态规划

1.状态定义（给定一个二维数组，数组的行代表字符m,列代表字符n）

那我们在二维数组[ i ][ j ]的位置表示字符串m的前i个字符与字符串n的前j个字符的最长公共子串的长度

2.状态转移：

根据状态定义，我们知道在一个判断中无非有两种情况：第i个字符与第j个字符相同；第i个字符与第j个字符不同；

• 第i个字符与第j个字符相同，那么[ i ][ j ]的位置可存储的数据就有两个选择，一个是[ i ][ j ]，另一个是[ i-1 ][ j-1 ]+1 即表示字符串m的前i-1个字符与字符串n的前j-1个字符的最长公共子串的长度+当前位置的一个相同字符。故这种情况下状态转移方程为dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j-1]);
• 第i个字符与第j个字符不同,我们就可以保存之前的公共子序列的最大长度，那之前的位置有谁呢？即当前位置的上面位置和左边位置即[i-1][j]   ; [i][j-1]
• 故这种情况下状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

3.结果：

顾名思义：结果将保存在二维数字最右下角 

 代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        int len1=str1.size();
        int len2=str2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        //str1的前i位和str2的前j位所拥有的最大的公共字符串的个数
        for(int i=0;i<len1;++i)
        {
            for(int j=0;j<len2;++j)
            {
                if(str1[i]==str2[j])
                {
                    dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1]);
                }
                else
                {
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        cout<<dp[len1][len2]<<endl;
    }
    return 0;
}