当前位置：网站首页>1255. 得分最高的单词集合状态压缩动态规划

1255. 得分最高的单词集合状态压缩动态规划

2022-07-17 02:15:00 【钰娘娘】

方法：动态规划

计数，映射到26个字母
填充单个单词的得分情况，顺便验证能否用现有字符组成单词
尝试继续填写，dp前26代表占用字母数目，第27位代表得分

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];
      }

  }

时间复杂度：O(n*2^n)
空间复杂度：O(2^n)

原网站

版权声明
本文为[钰娘娘]所创，转载请带上原文链接，感谢
https://yuduanhun.blog.csdn.net/article/details/125826063