update: add some dp.

yangxingchen · yangxingchen · commit d661fd256b28 · 2021-01-21T17:45:59.000+08:00
diff --git a/DynamicProgramming/ChangeProblem/ChangeProblem.py b/DynamicProgramming/ChangeProblem/ChangeProblem.py
@@ -1,3 +1,10 @@
+'''
+Author: yangxingchen
+Date: 2020-04-14 11:08:53
+LastEditors: yangxingchen
+LastEditTime: 2021-01-21 12:07:56
+Description: 
+'''
 """
 &#25214;&#38646;&#38065;&#38382;&#39064;
 &#35201;&#27714;&#65292;&#20351;&#29992;&#30340;&#30828;&#24065;&#26368;&#23569;&#25214;&#39046;
@@ -14,35 +21,50 @@ def change_greedy(coin_list, money):
     return result
 
 def change_recursion(coin_list, money):
+    """
+    &#36882;&#24402;&#35299;&#27861;
+    Args:
+        coin_list (list): &#25214;&#38646;&#30340;&#21333;&#20803;&#21015;&#34920;
+        money (int): &#38656;&#35201;&#25214;&#22810;&#23569;&#38065;
+    Returns:
+        int: &#36820;&#22238;&#27425;&#25968;
+    """
     if money == 0:
         return 0
     best = -1
     for coin in coin_list:
-        if (coin <= money):
-            next_try = change_recursion(coin_list, money - coin)
-            if best < 0 or best > next_try + 1:
-                best = next_try + 1
+        if (coin > money):   # &#30828;&#24065;&#38754;&#20540;&#27604;&#38656;&#35201;&#25214;&#38646;&#30340;&#22823;&#65292;&#22240;&#27492;&#25214;&#19981;&#20102;
+            continue
+        next_try = change_recursion(coin_list, money - coin)
+        if best < 0 or best > next_try + 1:     # best&#21021;&#22987;&#21270;&#20250;&#20026;-1
+            best = next_try + 1
     return best
 
 def coinChange(coins, amount) -> int:
     MAX_INT = 999999999
+    # &#31532;&#19968;&#27493;&#65292;&#26500;&#24314;&#29366;&#24577;&#25968;&#32452;
     f = [0] * (amount + 1)
     f[0] = 0
-
+    # &#21010;&#20998;&#23376;&#38382;&#39064;&#65292;&#23376;&#38382;&#39064;&#65292;&#20026;&#65292;&#38656;&#35201;&#20351;&#29992;&#22810;&#23569;&#26522;&#30828;&#24065;&#25340;&#20986;27-a_k&#26522;&#30828;&#24065;
     for i in range(1, amount + 1):
+        # &#35745;&#31639;&#25340;&#20986;1&#12289;2...amount&#22359;&#38065;&#26368;&#23569;&#30340;&#24773;&#20917;&#12290;
+        # &#36825;&#31181;&#26041;&#24335;&#26159;&#20174;&#24213;&#23618;&#21040;&#19978;&#23618; &#19968;&#23618;&#23618;&#30340;&#26500;&#24314;
         f[i] = MAX_INT
         # last coin A[j]
         # f[i] = min {f[i-A[0] + 1], f[i - A[n - 1] + 1 ...]}
         for j in coins:
-            if i >= j and f[i - j] != MAX_INT:
+            if j > i:      # coins &#30340;&#20540;&#22823;&#20110;&#35201;&#25214;&#38646;&#30340;,&#36825;&#27425;&#24490;&#29615;&#23558;&#26080;&#25928;
+                continue
+            if f[i - j] != MAX_INT:    # &#36825;&#37324;&#20854;&#23454;&#23601;&#26159;&#36716;&#31227;&#26041;&#31243;&#20351;&#29992;&#20102;&#12290;
                 f[i] = min(f[i - j] + 1, f[i])
-    
+        # &#36716;&#31227;&#26041;&#31243;&#22914;&#19979;
+    print(f)
     return f[amount] if f[amount] != MAX_INT else -1
 
 if __name__ == "__main__":
-    coin_list = [1, 4, 6, 10]
-    n = 12
+    coin_list = [2, 5, 7]
+    n = 3
     # print(change_greedy(coin_list, n))
     # print(change_recursion(coin_list, n))
     # &#36138;&#24515;&#31639;&#27861;&#24050;&#32463;&#36798;&#19981;&#21040;&#27491;&#30830;&#30340;&#35299;&#31572;&#20102;
-    print(coinChange([1, 2, 5], 11))
+    print("&#26368;&#23569;&#20351;&#29992;%d&#26522;&#30828;&#24065;&#25340;&#20986;%d&#22359;&#38065;" % (coinChange(coin_list, n), n))
diff --git a/DynamicProgramming/LongestCommonSubsequence/LCS.py b/DynamicProgramming/LongestCommonSubsequence/LCS.py
@@ -1,37 +1,27 @@
+'''
+Author: yangxingchen
+Date: 2020-04-15 13:44:20
+LastEditors: yangxingchen
+LastEditTime: 2021-01-21 15:12:22
+Description: 
+'''
 def longestCommonSubsequence(text1, text2) -> int:
     m = len(text1)
     n = len(text2)
 
     if m == 0 or n == 0:
         return 0
-
-    dp1 = [[0] * (n + 1)] * (m + 1)     # m &#34892; n &#21015;&#30340;&#25968;&#32452;
+    # &#26500;&#24314;m&#34892;n&#21015;&#30340;&#25968;&#32452;
+    # dp1 = [[0] * (n + 1)] * (m + 1)     # m &#34892; n &#21015;&#30340;&#25968;&#32452;
     
     dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]
-    for i in dp1:
-        print("====")
-        print(i)
-    print("+++++++++++")
-    for i in dp:
-        print("====")
-        print(i)
-    # for i in range(m):
-    for i in range(len(text1)):
 
-        # for j in range(n):
-        #     if text2[j] != text1[i]:
-        #         dp[i + 1][ j + 1] = max(dp[i][j + 1], dp[i + 1][j])
-        #     else:
-        #         dp[i+1][j+1] = dp[i][j] + 1
+    for i in range(len(text1)):
         for j in range(len(text2)):
             if text1[i] != text2[j]:
                 dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
             else:
                 dp[i+1][j+1] = dp[i][j] + 1
-    # for i in range(m):
-    #     print("====")
-    #     print(i)
-    #     print(f[i])
 
     # dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]
     # for i in range(len(text1)):
diff --git a/DynamicProgramming/UniquePaths/up.py b/DynamicProgramming/UniquePaths/up.py
@@ -0,0 +1,39 @@
+'''
+Author: yangxingchen
+Date: 2021-01-21 16:06:16
+LastEditors: yangxingchen
+LastEditTime: 2021-01-21 17:41:55
+Description: 
+'''
+"""
+&#39064;&#30446;&#25551;&#36848;&#65292;&#32473;&#23450;m&#34892;n&#21015;&#30340;&#32593;&#26684;&#65292;&#26377;&#19968;&#20010;&#26426;&#22120;&#20154;&#20174;&#24038;&#19978;&#35282;&#65288;0&#65292;0&#65289;&#20986;&#21457;&#65292;&#27599;&#19968;&#27493;&#21487;&#20197;&#21521;&#19979;&#25110;&#32773;&#21521;&#21491;&#65292;
+&#38382;&#65306;&#26377;&#22810;&#23569;&#31181;&#19981;&#21516;&#30340;&#26041;&#24335;&#36208;&#21040;&#21491;&#19979;&#35282;&#12290;
+"""
+
+def unique_path(m, n) -> int:
+    if m <= 0 or n <=0:
+        return 0
+    # &#29702;&#35770;&#19978;&#65292;&#36825;&#31181;&#39064;&#30446;&#26500;&#36896;&#19968;&#20010;&#19968;&#32500;&#25968;&#32452;&#20063;&#21487;&#20197;
+    # &#38656;&#35201;&#20998;&#26512;&#20986;&#36716;&#31227;&#26041;&#31243;&#65292;
+    # &#26426;&#22120;&#20154;&#26368;&#21518;&#19968;&#27493;&#35201;&#19981;&#26159;&#24448;&#19979;&#65292;&#35201;&#19981;&#26159;&#24448;&#21491;&#36793;
+    # &#20196;f(x, y) &#34920;&#31034;&#36208;&#21040;x&#65292;y&#30340;&#27493;&#25968;&#65292;&#37027;&#20040;f(x+1, y+1) = f(x, y+1) + f(x+1, y)
+
+    # &#24320;&#29366;&#24577;&#25968;&#32452;
+    dp = [[0]*(n+1) for _ in range(m+1)]
+    # &#26500;&#24314;&#21021;&#22987;&#29366;&#24577;
+    # dp = 1
+    for x in dp:
+        print(x)
+    for i in range(1, m+1):
+        for j in range(1, n+1):
+            if j == 1 or i == 1:
+                dp[i][j] = 1        # &#21021;&#22987;&#21270;&#65292;&#25226;&#21021;&#22987;&#21270;&#25918;&#21040;&#20102;&#36825;&#37324;
+                continue
+            print(i, j, '===')
+            dp[i][j] = dp[i][j -1] + dp[i-1][j]
+    for x in dp:
+        print(x)
+    print(dp[m][n])
+
+if __name__ == "__main__":
+    unique_path(3, 4)
