动态规划穷举的两种视角 :: labuladong的算法小抄

[giscus[bot]]

动态规划穷举的两种视角 :: labuladong的算法小抄

https://labuladong.gitee.io/algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-2526f/

[SUPER123695]

😵

[Larry-Wendy]

妙啊

[rrxsir]

喵啊

[hughxx]

东哥，可是我感觉紧界还是一样的，只是前一个上界算大了一点。总的态数一样的，第一种多了循环少了递归，第二种少了循环多了递归。

[CarlLy7]

多了递归但是递归里面没有循环啊

[CarlLy7]

而且每次递归问题规模都是缩小的

[FrancisDrakeII]

提壶灌顶

[CarlLy7]

打卡。 什么样的动态规划问题能够抽象成经典的「球盒模型」呢？ 我的思考是：匹配问题，给定的要进行匹配的源数据中会出现重复数据而且位置顺序不固定，来和给定的目的进行匹配的时候

[CarlLy7]

想咨询一下这里的重叠子问题的现象啥时候出现

[newlifehaonan]

按照东哥这篇文章中一眼看出重叠子问题的思路
站在s的视角分析

dp() {
    dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j) #1
    dp(s, i + 1, t, j) #2
}

如何从状态 (i, j) 转移到状态(i +1, j + 1) 至少可以有两种方法 (i, j) -> #1 -> #2, 或者 （i, j) -> #1 -> #1，或者(i, j) -> #2 -> #1 所以必须有重叠子问题.

站在t的视角分析，应为有for 循环，i 可以有k个不同的取值，转移方程为dp(s, k + 1, t, j + 1)， 所以重叠子问题更多.

[laoyoutiao237]

第一种办法前处理一下也可以优化掉遍历的for循环:

int numDistinct(string s, string t) {
        int n = s.size(), m = t.size(), memo[n][m];
        memset(memo, -1, sizeof memo);
        vector<vector<int>> index(128);
        //先记录一下相同元素的下标
        for(int i = n - 1; i >= 0; --i){
            int d = s[i];
            index[d].emplace_back(i);
        }

        function<int(int, int)> dp = [&](int i, int j)->int{
            if(j == m) return 1;
            if(m - j > n - i) return 0;
            if(memo[i][j] != -1) return memo[i][j];
            int ret = 0;

            for(int k : index[t[j]]){
                if(k < i) break;
                //站在 篮子 的视角选择 球
                ret += dp(k + 1, j + 1);
            }

            memo[i][j] = ret;
            return ret;
        };
        return dp(0, 0);
    }

[yimuu]

迭代

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;  // s 和 t 都为空的时候个数为 1
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s.charAt(i) != t.charAt(j)) {
                    dp[i][j] = dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j] + dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }  
}

[ConfuciusSaid]

我觉得dp[i]可以表示t[0]~t[i]在s中的子序列个数，13行代码就写完了，运行速度也更快
（初学，不太会动规，状态转移方程和时间复杂度我都不会分析）

class Solution {
    public int numDistinct(String ss, String ts) {
        char[] s = ss.toCharArray(), t = ts.toCharArray();
        int[] dp = new int[t.length];
        for(int i = 0, len = 0; i < s.length; i++) {
            if(len < dp.length && s[i] == t[len]) len++;
            for(int j = len - 1; j >= 0; j--)
                if(s[i] == t[j])   //新字母与子序列t[0]~t[j]最后一个字母相同，说明t[0]~t[j-1]与新字母也可以组出子序列t[0]~t[j]
                    dp[j] = dp[j] + (j > 0 ? dp[j - 1] : 1);  //dp[j]+=dp[j-1]：子序列t[0]~t[j]的个数加上t[0]~t[j-1]的个数
        }
        return dp[dp.length - 1];
    }
}

[wxnlzs]

res += dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j);
这个"+=",去掉加号也是可以的

[wjplc]

太妙了，我觉得我下次依然想不出来

[JeanYang2]

115.不同的子序列Python版打卡

class Solution:
def numDistinct(self, s: str, t: str) -> int:
self.memo=[[-1 for _ in range(len(t))]for _ in range(len(s))]
res=self.dp(s,t,0,0)
return res

def dp(self,s,t,i,j):
    if j==len(t):
        return 1
    if len(s)-i<len(t)-j:
        return 0
    if self.memo[i][j]!=-1:
        return self.memo[i][j]
    if s[i]==t[j]:
        self.memo[i][j]=self.dp(s,t,i+1,j+1)+self.dp(s,t,i+1,j)
    else:
        self.memo[i][j]=self.dp(s,t,i+1,j)
    return self.memo[i][j]