64
这道题用二维dp解思路就很清晰了,dp[i][j]表示i、j处的最小值,这个最小值是左边dp和上边dp的最小数再加上当前位置的元素值。初始化时要先对第一行和第一列初始化。
5
这道题也是二维dp,dp数组的含义是在i,j这个区间内如果是回文串那就返回true,否则返回false。递推关系是假设当前区间是[i,j],如果[i+1,j-1]的区间是回文串,当两端的元素也是回文串的时候,那么当前的区间就是回文串了。
1143
这道题也是用二维dp做,dp[i][j]的含义是text1区间[0,i-1]与text2[0,j-1]的区间内最长公共子序列长度是dp[i][j]。递推关系是,如果text1[i-1]==text2[j-1],那么dp[i][j]=dp[i-1][j-1]+1,否则dp[i][j]=max(dp[i-1][j],dp[i][j-1]),这里与前一个区间进行比较的含义是指当前元素已经不相等了,要取不包含这个元素的情况下最长的序列。