# 动态规划专题(Special topic of dynamic planning)-其他

## 动态规划专题(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)
``````