From 2749e059084b99737d79aadd92521023b0f65f56 Mon Sep 17 00:00:00 2001 From: chai Date: Thu, 24 Jun 2021 16:41:21 +0800 Subject: *dp --- Assets/Algorithms/Recursion/Recursion_DP.cs | 106 ++++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) create mode 100644 Assets/Algorithms/Recursion/Recursion_DP.cs (limited to 'Assets/Algorithms/Recursion/Recursion_DP.cs') 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[] A, T[] B, ref List result) where T : IEquatable, 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[] A, T[] B, ref List result) where T : IEquatable, 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 -- cgit v1.1-26-g67d0