1255. Dynamic programming for state compression of the word set with the highest score

Method ： Dynamic programming

1. Count , Mapping to 26 Letters
2. Fill in the score of a single word , By the way, verify whether you can use existing characters to form words
3. Try to continue filling ,dp front 26 Represents the number of occupied letters , The first 27 Delegate scores

class Solution {
      public long sellingWood(int m, int n, int[][] prices) {
          long[][] dp = new long[m+1][n+1];
          for(int [] price:prices){
              dp[price[0]][price[1]]=price[2];
          }
        
          for(int i = 1; i <= m; i++){
              for(int j = 1; j <= n; j++){
                    for(int t = 0 ; t<=j;t++) dp[i][j]=Math.max(dp[i][j],dp[i][t]+dp[i][j-t]);
                    for(int t = 0 ; t<=i;t++) dp[i][j]=Math.max(dp[i][j],dp[t][j]+dp[i-t][j]);
              }
          }
          return dp[m][n];
      }

  }

Time complexity ：O(n*2^n)
Spatial complexity ：O(2^n)