diff options
Diffstat (limited to 'Assets/Algorithms/Recursion/Recursion_DP.cs')
| -rw-r--r-- | Assets/Algorithms/Recursion/Recursion_DP.cs | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/Assets/Algorithms/Recursion/Recursion_DP.cs b/Assets/Algorithms/Recursion/Recursion_DP.cs new file mode 100644 index 0000000..a0205ba --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_DP.cs @@ -0,0 +1,106 @@ +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;
+ }
+
+ }
+}
\ No newline at end of file |