PHP算法合辑之动态规划

最长递增子序列

1、状态转移方程：$dp[$i] = $dp[$j] +1；
解读：既然是递增，意味着当前的个数等于前一个小于自己的值所对应的个数加1；
LCpage：https://leetcode.com/problems/longest-increasing-subsequence/submissions/

// 输入：nums = [10,9,2,5,3,7,101,18]
// 输出：4
// 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
function getLis($n) {
    $dp=[];
    for ($i=0; $i < count($n); $i++) { 
        $dp[$i]=1;
        for ($j=0; $j < $i; $j++) { 
            if ($n[$i]>$n[$j]) {
                $dp[$i] = max($dp[$i], $dp[$j]+1);
            }
        }
    }
    return max($dp);
}

$nums = [0,1,0,3,2,3];
print_r(
    array(
        getLis($nums),
    ),
);die;

718. 重复子数组的最大长度

官方解答：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/
LCpage：https://leetcode.com/problems/maximum-length-of-repeated-subarray/submissions/
动态规划解法：
1、状态转移方程：$dp[$i][$j] = $dp[$i+1][$j+1] +1；
2、基于上面的公式，循环方式是索引从大到小，倒排；

    function findLength($a, $b) {
        $ans=0;
        $dp=[];
        for ($i=count($a)-1; $i >=0; $i--) { 
            for ($j=count($b)-1; $j >=0 ; $j--) { 
                $dp[$i][$j]=0;
                if ($a[$i]===$b[$j]) {
                    $dp[$i][$j] = ($dp[$i+1][$j+1] ?? 0)+1;
                    $ans=max($dp[$i][$j], $ans);
                }
            }
        }
        return $ans;
    }

滑动窗口解法：

class Solution {
    function findLength($a, $b) {
        $ans=0;
        $ca=count($a);
        $cb=count($b);
        for ($i=0; $i < $ca; $i++) { 
            $aStart = $i;
            $bStart = 0;
            $loopLen = min($cb, $ca-$i);
            $subAns = $this->subLoop($a, $b, $aStart, $bStart, $loopLen);
            $ans=max($subAns, $ans);
        }
        for ($i=0; $i < $cb; $i++) { 
            $aStart = 0;
            $bStart = $i;
            $loopLen = min($ca, $cb-$i);
            $subAns = $this->subLoop($a, $b, $aStart, $bStart, $loopLen);
            $ans=max($subAns, $ans);
        }
        return $ans;
    }   
    function subLoop($a, $b, $aStart, $bStart, $loopLen) {
        $ret=0;
        $k = 0;
        for ($s=0; $s < $loopLen; $s++) { 
            if ($a[$aStart+$s]===$b[$bStart+$s]) {
                $k++;
                $ret=max($k, $ret);
            } else {
                $k=0;
            }
        }
        return $ret;
    }
}
// 上面的 滑动窗口 写法其实是如下解法【抽取公共方法】后的版本：
function findLength($a, $b) {
    $acnt=count($a);
    $bcnt=count($b);
    $ans=0;
    for ($i=0; $i < $acnt; $i++) { 
        $loopNum = min($acnt-$i, $bcnt);
        $t=0;
        for ($k=0; $k < $loopNum; $k++) { 
            if ($a[$k+$i]==$b[$k]) {
                $t++;
                $ans=max($t, $ans);
            } else {
                $t=0;
            }
        }
    }

    for ($i=0; $i < $bcnt; $i++) { 
        $loopNum = min($bcnt-$i, $acnt);
        $t=0;
        for ($k=0; $k < $loopNum; $k++) { 
            if ($b[$k+$i]==$a[$k]) {
                $t++;
                $ans=max($t, $ans);
            } else {
                $t=0;
            }
        }
    }
    return $ans;
}

最长公共子序列

// i、j 从1开始loop（即dp中存的是自然理解的截止位置，1到n的最长序列值，而非0开始的数组下标）
function longestCommonSubsequence($text1, $text2) {
    $t1=str_split($text1);
    $t2=str_split($text2);
    $tc1=count($t1);
    $tc2=count($t2);
    $dp=[];
    for ($i=1; $i <= $tc1; $i++) { 
        for ($j=1; $j <= $tc2; $j++) {
            if ($t1[$i-1]==$t2[$j-1]) {
                $dp[$i][$j] = ($dp[$i-1][$j-1]??0)+1;
            } else {
                $dp[$i][$j] = max($dp[$i-1][$j]??0, $dp[$i][$j-1]??0);
            }
        }
    }
    return $dp[$tc1][$tc2];
}
// i、j 从0开始loop
function longestCommonSubsequence($text1, $text2) {
        $alist=str_split($text1);
        $blist=str_split($text2);
        $ac=count($alist);
        $bc=count($blist);
        $dp=[];
        for ($i=0; $i < $ac; $i++) { 
            for ($j=0; $j < $bc; $j++) { 
                if ($alist[$i]==$blist[$j]) {
                    $dp[$i][$j]=($dp[$i-1][$j-1]??0)+1;
                } else {
                    $dp[$i][$j]=max(($dp[$i][$j-1]??0), ($dp[$i-1][$j]??0));
                }
            }
        }
        return $dp[$ac-1][$bc-1];
    }

不相交的线

LCpage：https://leetcode.com/problems/uncrossed-lines/submissions/

function maxUncrossedLines($nums1, $nums2) {
    $c1=count($nums1);
    $c2=count($nums2);
    $dp=[];
    for ($i=0; $i < $c1; $i++) { 
        for ($j=0; $j < $c2; $j++) { 
            if ($nums1[$i]==$nums2[$j]) {
                $dp[$i][$j]=($dp[$i-1][$j-1]??0)+1;
            } else {
                $dp[$i][$j]=max(($dp[$i][$j-1]??0), ($dp[$i-1][$j]??0));
            }
        }
    }
    return $dp[$c1-1][$c2-1];
}