动态规划

动态规划算法通常用于求解具有某种最优性质的问题 这类问题中, 可能会有许多可行解. 每一个解都对应一个值, 希望找到具有最优值的解

• 动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解.
• 与分治法不同的是, 适合动态规划求解的问题, 经分解得到的子问题往往不是互相独立的. 用分治法得到的子问题数目太多, 有些子问题被重复计算了很多次, 如果能保存已解决的子问题的答案, 而在需要的时候找出已求得的答案, 就可以避免重复大量的计算

动规五部曲

• 理解dp数组的含义，以及下标的含义
• 得到递推公式
• dp数组如何初始化
• 确定遍历顺序
• 当出现问题了，要学会打印dp数组

---

---

过河卒

❓ 为什么不能用广度搜索

• 实测20,20的时候跑不出来, 仔细想想, 因为结果要的是到终点的路径条数, 意味着每次经过一个点都要重复计算, 因为每重复算都是来自新的一条路, 所以考虑能不能不要重复计算

解题思路: 如果将每个点有个数组, 包含的是到这个点的路径条数有多少会怎样?

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN=21;
int dp[MAXN][MAXN];
int vis[MAXN][MAXN];
int zhx,zhy,mx,my;
 
int mal[][2]={
    /*{0,0},*/{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}
};
 
// bool iszhuang(int x,int y){
//     for(int i=0;i<9;i++){
//         if(x==mx+mal[i][0] && y==my+mal[i][1])
//             return true;
//     }
//     return false;
// }
 
int main(){
 
    cin>>zhx>>zhy>>mx>>my;
 
    vis[mx][my]=1;
    for(int i=0;i<8;i++){
        int xt=mx+mal[i][0];
        int yt=my+mal[i][1];
        if(xt>=0 && yt>=0 && xt<=zhx && yt<=zhy) vis[xt][yt]=1;
    }
 
 
    dp[0][0]=1;
    for(int i=0;i<=zhx;i++){
        for(int j=0;j<=zhy;j++){
            // if(!iszhuang(i,j)){
            //     if(i==0 && j!=0){
            //         dp[i][j]+=dp[i][j-1];
            //         continue;
            //     }else if(i!=0 && j==0){
            //         dp[i][j]+=dp[i-1][j];
            //         continue;
            //     }else if(i!=0 && j!=0){
            //         dp[i][j]+=dp[i-1][j]+dp[i][j-1];
            //     }
            // }else{
            //     dp[i][j]=0;
            // }
            if(i) dp[i][j]+=dp[i-1][j];
            if(j) dp[i][j]+=dp[i][j-1];
            if(vis[i][j]) dp[i][j]=0;
        }
    }
    cout<<dp[zhx][zhy];
 
    return 0;
}

最后一段注释, 考虑一下, 0不0的都可以用这样的语句简单完成