动态规划专题(Special topic of dynamic planning)

爬楼梯

//从前往后遍历
dp[1]=1
dp[2]=2
dp[i]=dp[i-1]+dp[i-2]

最长回文子串

//从小串到大串的遍历顺序
dp[i][i] = true;
if (j-i<3&&s[i]==s[j])   dp[i][j] = true;
dp[i][j] = (dp[i + 1][j - 1] and s[i]==s[j])

不同路径

//一行一行遍历(一列一列遍历)
dp[i][1]=1、dp[1][j]=1
dp[i][j]=dp[i-1][j]+dp[i][j-1]

最小路径和

//一行一行遍历(一列一列遍历)
dp[i][0]=0、dp[0][j]=0
dp[m][n]=min(dp[m-1][n],dp[m][n-1])+grid[m][n]

跳跃游戏

//由前往后(由后往前)
dp[0]=true
dp[end]=(dp[i] and nums[i]>end-i)
————————

climb stairs

//从前往后遍历
dp[1]=1
dp[2]=2
dp[i]=dp[i-1]+dp[i-2]

Longest Palindromic Substring

//从小串到大串的遍历顺序
dp[i][i] = true;
if (j-i<3&&s[i]==s[j])   dp[i][j] = true;
dp[i][j] = (dp[i + 1][j - 1] and s[i]==s[j])

Different paths

//一行一行遍历(一列一列遍历)
dp[i][1]=1、dp[1][j]=1
dp[i][j]=dp[i-1][j]+dp[i][j-1]

Minimum path sum

//一行一行遍历(一列一列遍历)
dp[i][0]=0、dp[0][j]=0
dp[m][n]=min(dp[m-1][n],dp[m][n-1])+grid[m][n]

Jumping game

//由前往后(由后往前)
dp[0]=true
dp[end]=(dp[i] and nums[i]>end-i)