Assets/Algorithms/Recursion/Recursion_DP.cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
using UnityEngine;

// 动态规划算法
namespace AlgorithmCollection.Recursion
{

    public static partial class RecursionHelper
    {
        //#region 动态规划框架
        //private static void DP()
        //{

        //}
        //#endregion

        //最长公共子串
        // longest common subpart
        public static void FindLCSP<T>(T[] A, T[] B, ref List<T> result) where T : IEquatable<T>, IComparable
        {
            int end = 0;                                       
            int maxLen = 0;                                    
            int[,] dp = new int[A.Length, B.Length]; // 记录以A[i],B[j]结尾的子串的最长公共子串长度
            for(int i = 0; i < A.Length; ++i)                 
            {                                                 //          1,             A[i]==B[j] && (i==0 || j==0)
                for (int j = 0; j < B.Length; ++j)            //dp[i,j] = dp[i-1,j-1]+1, A[i]==B[j] && i!=0 && j!=0
                {                                             //          0,             A[i]!=B[j] 
                    if(A[i].Equals(B[j]))                     
                    {                                        
                        if (i == 0 || j == 0)                 //   a b c b c e d
                            dp[i, j] = 1;                     // a 1 0 0 0 0 0 0
                        else                                  // c 0 0 1 0 1 0 0
                            dp[i, j] = dp[i - 1, j - 1] + 1;  // b 0 1 0 2 0 0 0
                        if (maxLen < dp[i, j])                // c 0 0 2 0 3 0 0
                        {                                     // b 0 1 0 3 0 0 0
                            maxLen = dp[i, j];                // c 0 0 2 0 4 0 0
                            end = i;                          // e 0 0 0 0 0 5 0
                        }                                     // f 0 0 0 0 0 0 0
                    }
                }
            }                                                 
            if(maxLen > 0)
            {
                for (int i = 0; i < maxLen; ++i)
                {
                    result.Add(A[end - maxLen + 1 + i]);
                }
            }
        }

        //最长公共子序列
        // longest common subsequence
        public static void FindLCSS<T>(T[] A, T[] B, ref List<T> result) where T : IEquatable<T>, IComparable
        {
            int[,] dp = new int[A.Length, B.Length]; // 记录[0-i]和[0-j]两个子串的最长公共子序列长度
            int max = 0;
            for (int i = 0; i < A.Length; ++i)                //          1,                        A[i]==B[j] && (i==0 || j==0)
            {                                                 //dp[i,j] = dp[i-1,j-1]+1,            A[i]==B[j] && i!=0 && j!=0
                for(int j = 0; j < B.Length; ++j)             //          0,                        A[i]!=B[j] && (i==0 || j==0)
                {                                             //          max(dp[i,j-1],dp[i-1,j]), A[i]!=B[j] && i!=0 && j!=0
                    if (A[i].Equals(B[j]))
                    {                                          //   a b c b c e d
                        if (i == 0 || j == 0)                  // a 1 1 1 1 1 1 1
                            dp[i, j] = 1;                      // c 1 1 2 2 2 2 2
                        else                                   // b 1 2 2 3 3 3 3
                            dp[i, j] = dp[i - 1, j - 1] + 1;   // c 1 2 3 3 4 4 4
                        if(max < dp[i, j])                     // b 1 2 3 4 4 4 4
                        {                                      // c 1 2 3 4 5 5 5
                            max = dp[i, j];                    // e 1 2 3 4 5 6 6
                            result.Add(A[i]);                  // f 1 2 3 4 5 6 6
                        }
                    }
                    else
                    {
                        if (i == 0 || j == 0)
                            dp[i, j] = 0;
                        else 
                            dp[i, j] = Algorithms.Max(dp[i - 1, j], dp[i, j - 1]);
                    }
                }
            }
            Debug.Log(max);
        }

        // 计算最大子段和
        public static int CalMaxSum(int[] nums)
        {
            int n = nums.Length;
            int max = int.MinValue;
            int sum = int.MinValue; //dp
            for(int i = 0; i < n; ++i)
            {
                if (sum > 0)
                    sum += nums[i];
                else
                    sum = nums[i];
                max = Algorithms.Max(max, sum);
            }
            return max;
        }


    }
}